Why quick sort is unstable

Question

I know there are several similar posts, but none of the answers are satisfying, which is why I want to ask this question again.

Consider the code below. It is my implementation of quick sort according to CRLS Introduction to Algorithms

int partition(int* a, int s, int e)
{
    int pivot = a[e];
    int q = s-1;
    for (int i = s; i <= e; i++)
    {
        if (a[i] <= pivot) {
            q++;
            int tmp = a[q];
            a[q] = a[i];
            a[i] = tmp;
        }
    }
    return q;
}

void quickSort(int* a, int s, int e)
{
    if (e > s) {
        int q = partition(a, s, e);
        quickSort(a, s, q-1);
        quickSort(a, q+1, e);
    }
}

Stable sorting algorithms maintain the relative order of records with equal keys (i.e., values). I don't understand why quick sort is not one of them. Although there are swaps between unadjacent elements in it, but I still don't see why that will cause unstability. I really hope someone could give examples to explain this.

Thank you.

Answer 1

In stable sorting algorithms,the swapping or spring occurs only with adjacent elements. For example in mergesort,the elements are made into units of one then, sorted accordingly using merge function .I think if u consider linear sort,its self explanatory. But that's not the case in quick sort.

Answer 2

try [ 1,1,1,5,5,5,5,1,1,1,4], pivot is 4 ,and when i meets the stronger "1",it swaps the first 5 with this "1"