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])
         
     exchange(A[i+1],A[r]); 
     return i+1;
   }

Aubert

it means that when two elements have the same key that is when two key are equall then it maintains their orignal order?? – Aubert

What language is this supposed to be? There seem to be spelling and parenthesis/bracket errors (together with misleading indentation) in your code, as well as spelling and grammar errors in your text. – Feigned

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.

Larry

Can you please explain in which condition it is not stable? – Syphilis

Here's a good description of stable sort. In stable sort, if two items compare as equal, their relative order is preserved. If my example sort were stable, the 9's would have remained in order throughout the sort. But they didn't. The first and third 9's were swapped. The swapping of equal values is exactly the condition in which this sort is not stable. Does that help? – Larry

Rose Perrone : Thanks for the explanation. When the equal values are swapped the sorting will no longer be stable. Is there any specific input pattern from which we can derive whether the input, if sorted, will not be stable? – Syphilis

There are many input patterns that swap equal values. Try taking an array with three 9's and one 1, with a partition value of 4, run through the algorithm, and you'll find you'll swap 9's. You can try out a variety of arrays that contain repeated numbers, and observe whenever a swap causes you to change the order of any of the repeated numbers. – Larry

Very clear. I think the unstable example is in the paragraph itself: Consider the following array where 4 is the pivot and you will see why it is unstable. 9₁,9₂,9₃,1,4 – Pacemaker

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.

Postlude

but if we follow above partioning algo then i dont see there is any loss of stability ,so can you plz give a set of test data which can demonstrate that it is unstable.. – Aubert

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.

Semanteme

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.

Sandglass

Can you make quicksort stable without changing the algorithm so that it's not recognizably quicksort? Not being facetious here, just wondering? – Recede

quicksort on linked lists is stable. You take the first element as the pivot, and then partition by appending to the two parts. Relative order will be preserved in each sublist, so that kind of quicksort is stable. – Anesthesia

but if we follow above partioning algo then i dont see there is any loss of stability ,so can you plz give a set of test data which can demonstrate that it is unstable. – Aubert

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

Cestoid

If it's not stable when all elements are the same, then it's not stable. – Arethaarethusa

@Joe: That special case can be handled in O(n) time, so it does not affect the O(n*log(n)) running time. – Cestoid

I assume you mean "all elements equivalent". If all elements are the same, there's only one permutation possible, which by definition is always sorted. – Sheikdom

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.

Vociferate

Answer 7

From Wikipedia:

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

Achievement

but note that it can be made stable (and less quick) with a proper partitioning algorithm and good choice of the pivot element. – Sandglass

So it's pick-your-poison, less stability or reduced quickness. – Achievement

can you plz give a set of test data which can show that following the above partioning scheme will led to loss stability in quicksort! – Aubert

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.

Shalna