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.

回答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.

回答2:

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

回答3:

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

回答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.