Talk:Quicksort

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)

--

I agree with the original poster of this thread, the algorithm as written does not correctly handle duplicate pivot elements.

I have written a simple working version in C++ that showed up a few issues in the algorithm as written.

A couple of points:

1. Notably, 'storeIndex' can be incremented past the end of the segment, in which case the final swap will do the wrong thing. This must be checked for.

2. The pivot element cannot be excluded from the sort result (ie. the part stating to recursively sort two subarrays: [0, pivotIndex-1] and [pivotIndex+1, end] is wrong. It should read [0, pivotIndex-1] and [pivotIndex, end]. Modifying the real code and observing the unsorted results below can verify this.

   int partition(int* start, int* end, size_t pi, int pv)
   {
       swap(start[pi], *(end-1));
       
       int* store = start;
       for (int* i = start; i<end; ++i)
       {
           if (*i <= pv)
           {
               swap(*i, *store);
               ++store;
           }
       }
       if (store >= end)
           store = end -1;
       
       swap(*store, *(end - 1));    
       return store - start;
   }
   
   void sort(int* start, int* end)
   {
       size_t size = end - start;
       if (size < 2) 
           return;
       
       size_t pi = size / 2;
       size_t pv = start[pi];    
       pi = partition(start, end, pi, pv);   
       sort(start, start + pi);
       sort(start + pi, end);
   }

   -- Matthew Herrmann (Dec 1, 2010)

--

It's working, that's probably a problem with your implementation, like the way you're handling boundaries. I've done several tests using the following Python 3 script; note that the quicksort is implemented exactly as in the pseudo-code:

from random import randint

def partition(array, left, right, pivotIndex):
    pivotValue = array[pivotIndex]
    array[pivotIndex], array[right] = array[right], array[pivotIndex]
    storeIndex = left
    for i in range(left, right):    # left <= i < right
        if array[i] <= pivotValue:
            array[i], array[storeIndex] = array[storeIndex], array[i]
            storeIndex += 1
    array[storeIndex], array[right] = array[right], array[storeIndex]
    return storeIndex

def quicksort(array, left, right):
    if right > left:
        pivotIndex = int(left + (right - left) / 2)
        pivotNewIndex = partition(array, left, right, pivotIndex)
        quicksort(array, left, pivotNewIndex - 1)
        quicksort(array, pivotNewIndex + 1, right)

# Testing:
num_tests = int(input('Number of tests: '))
size = int(input('Length of array: '))
limit = int(input('Items ranging from 0 to ...? '))
failed = False
for i in range(num_tests):
    a = []
    for j in range(size):
        a.append(randint(0, limit))
    b = sorted(a)
    quicksort(a, 0, len(a) - 1)
    if a != b:
        failed = True
        break
if failed:
    print('Got/should be:\n{0}\n{1}'.format(a, b))
else:
    print('Sorted correctly.')

189.41.33.54 (talk) 00:33, 4 December 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)

"Note the left + (right-left)/2 expression. (left + right)/2 would seem to be adequate, but in the presence of overflow, [blah]"

How would (left + right)/2 seem adequate? BS. That would only work if left was zero, in which case, it equals right/2, which is the same as left + (right-left)/2 (for left = 0). True, right/2 might look correct at first. But since left is not always zero, neither this nor (left + right)/2 works. Additionally, imagining the latter to be adequate is absurd if you have any knowledge of arrays and indices. --84.62.36.217 (talk) 15:15, 27 September 2010 (UTC)

(left + right)/2 is absolutely correct in context. If we neglect integer overflow then left + (right-left)/2 = left/2 + right/2 = (left + right)/2 which are both obviously the middle of the array being sorted. I suppose if you for some reason suppose that / doesn't do integer division you might have problems, but otherwise I can't see your issue. Perhaps if you explained the issue and a suggestion for how to fix it without spewing vitriol we might improve the article. bou·le·var·dier (talk) 15:50, 27 September 2010 (UTC)

This is probably the link you were looking for: googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html 67.162.90.113 (talk) 20:21, 2 November 2010 (UTC)

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? —Preceding unsigned comment added by 75.27.121.68 (talk) 18:15, 20 September 2010 (UTC)

Do you mean the part which says
        select and remove a pivot value pivot from array
...? --CiaPan (talk) 06:14, 24 September 2010 (UTC)

Right, this is something that was right until it was changed in August. I changed it back a few days ago. As CiaPan mentions, the original pivot is removed from the array when it's selected. The equals case ensures that duplicates of the pivot element in the array are still sorted - if the equals case is not placed into either the lesser or greater sets, the duplicates of the pivot element disappear from the sorted array. This is something that was alluded to in the text before the algorithm but had been changed in the algorithm itself. bou·le·var·dier (talk) 08:03, 27 September 2010 (UTC)

Avoiding Unnecessary Swaps

Regarding the in-place partition function..

Question 1: Should "if array[i] ≤ pivotValue" be "if array[i] < pivotValue" instead? Why swap equal elements -- that's pointless. After all, if elements equal to pivotValue stay to the right of the pivot - that's still a valid partitioning result.

Question 2: Should "swap array[i] and array[storeIndex]" be "if (i != storeIndex) swap array[i] and array[storeIndex]" -- why swap with itself? That's even more pointless. —Preceding unsigned comment added by 131.107.0.98 (talk) 15:42, 25 October 2010 (UTC)

Answer 1: that doesn't matter, actually. Usually we don't have many equal items in the array, so skipping equal items gives no significant gain.
Generally the quicksort works quite poorly on arrays with lots of equal items. Those items lead to unbalanced partitioning results (often it is 'one and the rest') which causes a rapid growth of recursion depth. If you need to sort such arrays and want to use quicksort for it, consider some more sophisticated partitioning routine, which would give three sub-arrays: left one with items less than the pivot, central part with (possibly many) items equal to the pivot, and the right one with items greater than the pivot.

Answer 2: That is even more pointless. In optimistic case, partitioning routine would split the array into halves, which means approx. half of items are bigger than the pivot. So it's 1:2 chance the first item will get 'swapped' with itself, same 1:2 for the second one and so on... The expected number of self-swapped items for this case is 2.
For less optimistic case it might be bigger, anyway it is still a small number. Your change inserts additional code which is executed for every item swapped during partitioning to avoid a few self-swaps. That will effectively make the routine slower.
Your modification would bring some important speed-up if your input data are already sorted or 'almost' sorted. But in that case you can use other algorithms, which work better on such data than a very general quicksort.

CiaPan (talk) 21:54, 29 October 2010 (UTC)

Follow-up 1: So, changing from '<=' to '<' doesn't have any effect if all elements are different (obviously), and improves performance in presence of equal elements.. Why is it not a change worth making? Isn't most of quicksort analysis focused on how to improve its performance in the worst case? It seems to me that the argument for "Oh, quicksort isn't good for XYZ, so it's not worth improving it for XYZ" is like throwing out the baby with the bathwater. This is an optimization with 0 cost, but with benefits. Why does it not matter?

Follow-up 2: storeIndex would be == i, when the array is already partitioned/sorted appropriately. So, again, this is about improving the worst-case performance, avoiding a large number of pointless swaps. It all comes down to the cost of a CPU-register compare operation vs. a Swap (two memory reads&writes), which may be orders of magnitude apart. One would have to run some measurements to know, but dismissing this optimization outright is premature.

As a general comment, choosing a more appropriate sorting algorithm based on some euristics, is a different discussion entirely. —Preceding unsigned comment added by 67.243.31.51 (talk) 19:58, 31 October 2010 (UTC)

Answer 1
Yes, strictly speaking, you're right in that the change makes some improvement. What you miss is the fact, that the improvement is negligible compared to the huge loss of efficiency the routine suffers from equal elements. You want to consider the worst case – well, here it is: the worst case for Quicksort is an array of equal elements. In that case the routine performs one initial swap, then scans the given interval to be partitioned, and finally makes another swap. Your modification saves n−1 swaps, but can't help for necessary n−1 comparisons nor for the resulting one-to-(n−1) partitioning result. As a result the total cost in the worst case drops from $O(n^{2}){\text{ comparisons}}+O(n^{2}){\text{ swaps}}$ to $O(n^{2}){\text{ comparisons}}+O(n){\text{ swaps}}$, anyway it is still $O(n^{2})$. That's why I said it gives no significant gain.

Answer 2
If you consider things on the CPU internals level, you should also take the jumps prediction into account — additional conditional instruction makes another point where the CPU instruction pipeline may temporarily stop for re-filling; so the if is not just a register operation, but also a possible waste of time.
Another efficiency factor is a CPU cache: once a relatively small portion of data (an element of the array) has been read for comparison, it is already in the cache; swapping it with itself means overwriting it twice with the same data (for copying from A[storeIndex] to A[i] and for copying from A[i] to A[storeIndex]). Those writes do not change the memory contents, so they might well execute entirely in the cache; actually nothing would be written back to the main memory. The same applies to the 'temp' variable used during swap (provided that the cache works in the 'copy-back' mode and that 'cache misses' do not conflict with that particular location too often, which would force flushing it to the main memory). As a result you add instructions, which must be read and executed, in effort to reduce non–existent costs.

CiaPan (talk) 22:32, 2 November 2010 (UTC) (and 19:56, 4 November 2010 (UTC))

Since we're dealing with detail, I dispute your supposition of nothing being written back to main memory for the equivalent of A[i]:=A[j]; when i = j. When something is to be stored in the location corresponding to A[i] the buffering scheme will receive the value, and mark the location as "changed" so as later to write from the buffer to the main memory, etc. For this to not happen, the buffer/cache controller would have to be checking that the new value for A[i]'s location is different from the existing value, and only set "changed" if so. This is possible, but I doubt that it is done. For every write to memory. Computer hardware/firmware does not embody transcendent understanding, to wave hands at in awe. Similarly, how is the expression compiled? If say to a single instruction, Move x,y where x and y are addresses (or the names of registers, or the names of registers containing the addresses of the data to be moved) it is possible that within the microcode for the Move opcode a no-action would ensue if x = y. But the code may be more complex, as when an element of A is not a computer word.

Otherwise, idiot swaps take place. But code to check for and evade this effort on every swap is itself extra effort. It is better to evade these timewasters at a higher level... NickyMcLean (talk) 20:38, 4 November 2010 (UTC)

Wrong algorithm

Several of the statements on this page including the definition of the "simple" algorithm are quite baffling when considered in the context of Hoare's original 1962 paper about quicksort, which explicitly defined quicksort as an in-place algorithm that used in-situ exchanges to partition with the explicitly stated goal of minimizing memory consumption in order to improve performance. These characteristics are what makes the genuine quicksort algorithm quick. The "simple" algorithm described on this page captures none of these characteristics and, consequently, is far from quick. Specifically, it is orders of magnitude slower. Perhaps this "simple" algorithm should be stripped from this page along with the unjustified statements about its relative popularity and a citation to the authoritative primary source be added?