quicksort algorithm stability

Question

Quicksort is not stable, since it exchanges nonadjacent elements.

Please help me understanding this statement.

I know how partitioning works, and what stability is. But I cant figure out what makes the above as the reason for this to be not stable? Then I believe the same can be said for merge sort - though it is quoted to be a stable algorithm.

Contorted

This means that on multiple sorts, you are not guaranteed to have the same order of elements that resolve to the same equality. so if you have 1,1,2,3,5,6,7 , the two ones in the beginning may not be in a defined order - this matters more when you sort on a certain key for more complex objects, obviously – Roark

It is very well covered here – Purse

Answer 1

Consider what happens during the partition for the following array of pairs, where the comparator uses the integer (only). The string is just there so that we have two elements that compare as if equal, but actually are distinguishable.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

By definition a sort is stable if, after the sort, the two elements that compare as if equal (the two 4s) appear in the same order afterwards as they did before.

Suppose we choose 3 as the pivot. The two 4 elements will end up after it and the 1 and the 2 before it (there's a bit more to it than that, I've ignored moving the pivot since it's already in the correct position, but you say you understand partitioning).

Quicksorts in general don't give any particular guarantee where after the partition the two 4s will be, and I think most implementations would reverse them. For instance, if we use Hoare's classic partitioning algorithm, the array is partitioned as follows:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

which violates the stability of sorting.

Since each partition isn't stable, the overall sort isn't likely to be.

As Steve314 points out in a comment, merge sort is stable provided that when merging, if you encounter equal elements you always output first the one that came from the "lower down" of the two halves that you're merging together. That is, each merge has to look like this, where the "left" is the side that comes from lower down in the original array.

while (left not empty and right not empty):
    if first_item_on_left <= first_item_on_right:
       move one item from left to output
    else:
       move one item from right to output
move everything from left to output
move everything from right to output

If the <= were < then the merge wouldn't be stable.

Gastroscope

+1 - you could usefully add that in mergesort, the reason equal items keep their original order is because in each merge, you know which of the merged sequences came first in the original data - when you find equal items, you simply select the one from the first sequence rather than the second and the original ordering is preserved. So in a way, the items aren't equal WRT merging - the merge enforces an ordering based on original position when the values are equal. – Cheremkhovo

Very helpful - it makes sense now!! – Contorted

this example is best:) – Lindo

@Steve314. Wow! Are you still in this website please? – Spout

Answer 2

Consider the following array of pairs:

{(4,'first');(2,'');(1,'');(4,'second');(3,'')}

Consider 3 as pivot. During a run of Quick sort, the array undergoes following changes:

1. {(4,'first');(2,'');(1,'');(4,'second');(3,'')}
2. {(2,'');(4,'first');(1,'');(4,'second');(3,'')}
3. {(2,'');(1,'');(4,'first');(4,'second');(3,'')}
4. {(2,'');(1,'');(3,'');(4,'second');(4,'first')}
5. {(1,'');(2,'');(3,'');(4,'second');(4,'first')}

Clearly from the above, the relative order is changed. This is why quick sort is said to 'not ensure stability'.

Siouan

Answer 3

It will be like a user has a sorted array, and sorts by another column, does the sort algorithm always preserve the relative order of the elements that differ for the previous sort key but have the same value in the new sort key? So, in A sort algorithm which always preserves the order of elements (which do not differ in the new sort key) is called a "stable sort".

Cistercian

Answer 4

A sort is said to be stable if the order of equivalent items is preserved. The stability of quicksort depends on partitioning strategy. "Quicksort is not stable since it exchanges nonadjacent elements." This statement relies on the prerequisite that Hoare partitioning is used. This is a hoare partioning demo from Berkeley CS61b, Hoare Partitioning

You should know what "it exchanges nonadjacent elements " means.

Outsole