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.
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? Yes, naive quicksort is stable because the partitioning algorithm is stable since it maintains the relative ordering of equal items.
The Quicksort Algorithm is Not Adaptive, Can we make QuickSort Algorithm Adaptive? Yes, we can make it Adaptive very easily.
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.
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 4
s) 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 4
s 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.
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".
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With