Talk:Quicksort

Simple Pseudocode Error?

The concatenation appears to put the lesser table, the pivot record and the greater table together. However, just before it, the pivot record is included in the lesser table. That yields a double record for the pivot, no?

Correctness of the partition function?

Hello,

can somebody confirm the partition function is actually correct? When I look at the CLRS version and turn it into actual code it works, if I do the same with the Wikipedia version it doesn't.

  // CLRS version in pseudo code
  function partition(A, p, r)
     x = A[r]
     i = p - 1
     for j = p to r - 1
         if A[j] ≤ x 
             i = i + 1
             exchange A[i] with A[j]
     exchange A[i + 1] with A[r]
     return i + 1

   // CLRS version in Java
   public static int partition(int[] A, int p, int r) {
       int x = A[r];
       int i = p - 1;
       for (int j = p; j < r; j++) {
           if (A[j] <= x) {
               i = i + 1;
               exchange(A, i, j);
           }
       }
       exchange(A, i + 1, r);
       return i + 1;
   }

   // Wikipedia version in Java
   public static int partition(int[] array, int left, int right, int pivotIndex) {
       int pivorValue = array[pivorIndex];
       swap(array, pivotIndex, right);
       int storeIndex = left;
       for (int i = left; i < right; i++) {
           if (array[i] <= pivotValue) {
               swap (array, i, storeIndex);
               storeIndex = storeIndex + 1;
           }
       }
       swap(array, storeIndex, right);
       return storeIndex;
   }

Results:

   Input: [86, -28, -15, 70, -115]
   Wiki-Output: [86, -28, -15, -115, 70]
   CLRS-Output: [-115, -28, -15, 70, 86]  

—Preceding unsigned comment added by 24.215.230.83 (talk) 17:35, 31 December 2009 (UTC)

Wikipedia's code is incorrect

The in-place quicksort code currently on wikipedia is incorrect. Consider what happens when you try to sort [1,3,2]. (Your result will still be [1,3,2].)

Slythfox (talk) 07:25, 21 April 2010 (UTC)

The entry has been split by CiaPan (talk) to discuss both parts separately.

Really? Where is the error?

Let's see how it works. Assume the array is indexed from 1 to 3. We start with:
    quicksort( [1,3,2], 1, 3)
Then
    pivotIndex := 1 + (3-1)/2 = 2
and we call:
    partition( [1,3,2], 1, 3, 2)
        pivotValue := array[2] = 3
and the first swap makes
        array := [1,2,3]

The loop scans array items from left = 1 to right-1 = 2. They are both less than the pivotValue, so each of them gets swapped with itself (storeIndex is incremented along with i, the loop control variable), thus the whole loop changes nothing in the array. However as storeIndex gets incremented on every pass of the loop, it is finally equal 3. Then the last swap swaps the third item of the array with itself (storeIndex=3 and right=3).
The first partition call leaves the array sorted and returns storeIndex equal 3.

After return to the quicksort the pivotNewIndex is set to the returned value of 3, then the recursive call of quicksort( [1,2,..], 1, 2) swaps twice elements no.1 and 2, so it effectively doesn't change the array.

All remaining calls handle one-item or empty subarrays, so they do not affect the ordering. Finally the array gets sorted.

Can you show, how you got the final order of [1,3,2]? --CiaPan (talk) 08:46, 21 April 2010 (UTC)

Notice how the CLRS code initially sets the storeIndex (i in CLRS code) to right - 1 instead of right. It also does the storeIndex (i in CLRS code) before swapping. And lastly, CLRS and returns swaps storeIndex + 1 instead of storeIndex.

Slythfox (talk) 07:25, 21 April 2010 (UTC)

You don't read carefully enough. Both samples are equivalent. In fact they are almost the same. The only two differences are

1. the CLRS code assumes the rightmost item of the subarray being the pivot, while the wikipedia code allows the caller function to specify the pivot's index, and
2. the CLRS keeps its i less by 1 than Wiki's storeIndex — it initializes the variable with p–1 and increments before each swap in the loop (so, after the loop terminates, the variable is too small by 1, so we must add 1 to it before the final swap and before returning its value), while Wiki's code initializes the corresponding variable with the left value and increments it after each swap in a loop, so after the loop it is immediately ready for the final swap and return.

These differences affect the code efficiency but have no meaning for the algorithm correctness — although they're written different, on same input both routines handle same data in the same way (if we simplify the wiki code to always use pivotIndex := right) and consequently both routines give same results. That means both are correct (or none of them). --CiaPan (talk) 20:58, 21 April 2010 (UTC)

Goodness, I never considered #1. I implemented both the CLRS partition code and the wiki's partition code with some (but clearly not enough) consideration to how the storeIndex value was used when it came to recursion for each.

Slythfox (talk) 06:29, 22 April 2010 (UTC)

Images

Could someone please consider using this? http://corte.si/posts/code/visualisingsorting/index.html 84.182.107.93 (talk) 16:54, 9 February 2010 (UTC)

Their partition algorithm does not work on all data sets

The comparison "<" should probably be replaced by a "<=", but even that does not fix it.

In particular, if the set is: [ 3, 5, 8, 5, 2, 1, 9, 7, 4]

Then the 5 will incorrectly remain in index 1.

Does anyone have a correct algorithm which correctly accounts for duplicates of the pivot? —Preceding unsigned comment added by 75.85.57.215 (talk) 18:58, 9 March 2010 (UTC)

I'm not sure which comparison you are referring to. "<" doesn't exist in any of the pseudo-codes, except for one comment. An "imaginary" run seemed to sort the array correctly. Rami R 14:55, 10 March 2010 (UTC)

no, it doesn't. [9,8,5,7,6,5,4,5,3,2,1] with pivot =5, index = 5, results in [5,1,4,5,3,2,5,7,6,8,9]. —Preceding unsigned comment added by 95.65.28.117 (talk) 21:41, 11 March 2010 (UTC)

And this is a correct result of partitioning: the array has been reordered so that it contains the pivot (5) at some position (index 6) and all items less than or equal to the pivot in left subarray (indices 0 through 5) and all items greater than the pivot to the right from it (indices 7 through 10). Perfect partitioning.
You probably forgot, that the single partitioning does not complete sorting. To sort the array you need now to partition recursively both subarrays [5,1,4,5,3,2] and [7,6,8,9], then the resulting sub-sub-arrays, and so on until you step down to single-item parts. Then the task will be done. --CiaPan (talk) 21:41, 21 April 2010 (UTC)

Okay, I've implemented the pseudo-code in Java:

public class Quicksort{

	public static void swap(int[] array, int i, int j){
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}

	 public static int partition(int[] array, int left, int right,
		int pivotIndex){
		int pivotValue = array[pivotIndex];
		swap(array,pivotIndex,right); // Move pivot to end
		int storeIndex = left;
		for(int i=left;i<right;i++) // left ? i < right  
			if(array[i]<=pivotValue){
				swap(array,i,storeIndex);
				storeIndex++;
			}
		swap(array,storeIndex,right); // Move pivot to its final place
		return storeIndex;
	}

	 public static void quicksort(int[] array, int left, int right){
		if(right > left){
			int pivotIndex = (left+right)/2;
			int pivotNewIndex = partition(array, left, right, pivotIndex);
			quicksort(array, left, pivotNewIndex - 1);
			quicksort(array, pivotNewIndex + 1, right);
		}
	}

	public static void main(String[] args){
		int[] array={3, 5, 8, 5, 2, 1, 9, 7, 4};
		quicksort(array,0,array.length-1);
		for(int i=0;i<array.length;i++)
			System.out.print(" "+array[i]);
		System.out.print("\n");
	}
}

This code is no different than the pseudo-code, and it will correctly sort the array. You've probably implemented the pseudo-code wrong. Rami R 08:49, 12 March 2010 (UTC)

This partition function does not work correctly when pivotIndex is set to zero. --this unsigned comment was added 25 April 2010 by 67.183.108.57 (talk)

Can you give an example? Rami R 10:17, 27 April 2010 (UTC)

Parallelization

I think the parallelization section could use some more details. One thing that seems to be missing is how you'd combine the results from the p sublists. I'm guessing you'd do something similar to merge sort, but that doesn't seem right, because in the case where p = n, you'd end up with a linear insertion sort, which runs in O(n^2), which is actually slower than the standard non-parallel quicksort. Anyway, more details would be appreciated. Danielx (talk) 02:56, 28 April 2010 (UTC)

There's no 'combine'—once the array got partitioned it has a structure of
[ items less than or equal to X | item X | items greater than X ]
where X is the pivot. At that point the pivot is in its final position and no item from the left subarray needs moving to the right of the pivot and no item from the right subarray needs moving to the left of it. So the two subarrays, although not sorted yet, are combined already. No further 'combining' is needed, just sorting subarrays. --CiaPan (talk) 20:20, 28 April 2010 (UTC)

left + (right-left)/2

I just restored this code and added a small explanation of why it's needed. I know I've seen this problem described, I think by some Google blog entry on algorithms, but I don't remember where. I want to add "this is a somewhat theoretical problem, since it only arises when you are binary-searching an array with at least half the number of items in it that your integer type can represent, which means either that your integers are much shorter than your pointers; or your array doesn't actually fit in your RAM, in which case you're probably encountering disk seek latencies and should therefore use a B+-tree instead, you douchebag; or your array consists of single bytes, in which case you should probably encode it as a 256-word table instead of gigabytes of "aaaaaa"." But I think that would be "original research".

It may be that the paragraph I added would be better somewhere else.

Kragen Javier Sitaker (talk) 17:48, 28 August 2010 (UTC)