Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

quicksort algorithm stability

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.

like image 536
IUnknown Avatar asked Nov 21 '12 16:11

IUnknown


People also ask

Is quicksort a stable algorithm Why?

QuickSort is an unstable algorithm because we do swapping of elements according to pivot's position (without considering their original positions).

Is naive quicksort stable?

Is naive quicksort stable? Yes, naive quicksort is stable because the partitioning algorithm is stable since it maintains the relative ordering of equal items.

Is quicksort stable and adaptive?

The Quicksort Algorithm is Not Adaptive, Can we make QuickSort Algorithm Adaptive? Yes, we can make it Adaptive very easily.

Is Randomised quick sort stable?

Randomized quick sort is a stable sort. Explanation: Randomized quick sort like standard quick sort is also not a stable sorting algorithm. It is because the elements with the same values are not guaranteed to appear in the same relative order in the output sorted array.


2 Answers

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.

like image 122
Steve Jessop Avatar answered Sep 19 '22 17:09

Steve Jessop


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".

Please have a look of example

like image 42
Rahul Maurya Avatar answered Sep 19 '22 17:09

Rahul Maurya