Stability of quicksort partitioning approach

Question

Does the following Quicksort partitioning algorithm result in a stable sort (i.e. does it maintain the relative position of elements with equal values):

  partition(A,p,r)
  {
     x=A[r];
     i=p-1;
     for j=p to r-1
       if(A[j]<=x)
          i++;
          exchange(A[i],A[j])

       exchang(A[i+1],A[r]); 
     return i+1;
   }

Answer 1

There is one case in which your partitioning algorithm will make a swap that will change the order of equal values. Here's an image that helps demonstrate how your in-place partitioning algorithm works:

We march through each value with the j index, and if the value we see is less than the partition value, we append it to the light-gray subarray by swapping it with the element that is immediately to the right of the light-gray subarray. The light-gray subarray contains all the elements that are <= the partition value. Now let's look at, say, stage (c) and consider the case in which three 9's are in the beginning of the white zone, followed by a 1. That is, we are about to check whether the 9's are <= the partition value. We look at the first 9 and see that it is not <= 4, so we leave it in place, and march j forward. We look at the next 9 and see that it is not <= 4, so we also leave it in place, and march j forward. We also leave the third 9 in place. Now we look at the 1 and see that it is less than the partition, so we swap it with the first 9. Then to finish the algorithm, we swap the partition value with the value at i+1, which is the second 9. Now we have completed the partition algorithm, and the 9 that was originally third is now first.

Answer 2

Any sort can be converted to a stable sort if you're willing to add a second key. The second key should be something that indicates the original order, such as a sequence number. In your comparison function, if the first keys are equal, use the second key.

Answer 3

A sort is stable when the original order of similar elements doesn't change. Your algorithm isn't stable since it swaps equal elements.

If it didn't, then it still wouldn't be stable:

( 1, 5, 2, 5, 3 )

You have two elements with the sort key "5". If you compare element #2 (5) and #5 (3) for some reason, then the 5 would be swapped with 3, thereby violating the contract of a stable sort. This means that carefully choosing the pivot element doesn't help, you must also make sure that the copying of elements between the partitions never swaps the original order.

Answer 4

Your code looks suspiciously similar to the sample partition function given on wikipedia which isn't stable, so your function probably isn't stable. At the very least you should make sure your pivot point r points to the last position in the array of values equal to A[r].

You can make quicksort stable (I disagree with Matthew Jones there) but not in it's default and quickest (heh) form.

Martin (see the comments) is correct that a quicksort on a linked list where you start with the first element as pivot and append values at the end of the lower and upper sublists as you go through the array. However, quicksort is supposed to work on a simple array rather than a linked list. One of the advantages of quicksort is it's low memory footprint (because everything happens in place). If you're using a linked list you're already incurring a memory overhead for all the pointers to next values etc, and you're swapping those rather than the values.

Answer 5

If you need a stable O(n*log(n)) sort, use mergesort. (The best way to make quicksort stable by the way is to chose a median of random values as the pivot. This is not stable for all elements equivalent, however.)

Answer 6

Quick sort is not stable. Here is the case when its not stable.

5 5 4 8

taking 1st 5 as pivot, we will have following after 1st pass-

4 5 5 8

As you can see order of 5's have been changed. Now if we continue doing sorting it will change the order of 5's in sorted array.

Answer 7

From Wikipedia:

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Answer 8

One way to solve this problem is by not taking Last Element of array as Key. Quick sort is randomized algorithm.

Its performance highly depends upon selection of Key. Although algorithm def says we should take last or first element as key, in reality we can select any element as key.

So I tried Median of 3 approach, which says take first ,middle and last element of array. Sorts them and then use middle position as a Key.

So for example my array is {9,6,3,10,15}. So by sorting first, middle and last element it will be {3,6,9,10,15}. Now use 9 as key. So moving key to the end it will be {3,6,15,10,9}.

All we need to take care is what happens if 9 comes more than once. That is key it self comes more than once.

In such cases after selecting key as middle index we need to go through elements between Key to Right end and if any element is found same key i.e. if 9 is found between middle position to the end make that 9 as key.

Now in the region of elements greater than 9 i.e. loop of j if any 9 is found swap it with region of elements less than that is region of i. Your array will be stable sorted.