Quick Sort Recap: 2-way Partition, Counter-intuitive Details

Overview

I give C++ implementation of Quick Sort with counter-intuitive parts (e.g., loop termination,  stop at equal keys) explained and common practical improvements.

This is a quick recap of quick sort which I actually have learned over and over again and I decide to review all the coding and implementation details based on the course material of Algorithm Part 1 from Coursera in which professor actually did not explain everything clearly to my knowledge.

2-way Partition Quick Sort

I give the C++ implementation first and explain the coding details, like why it return j rather than i in partition, why the loop terminates when i >= j rather than when i > j and so on.

int partition(int naryNumbers[], int nLo, int nHi) {
	int i = nLo, j = nHi + 1;
	int nPivot = naryNumbers[nLo];
	while (true) {
		while (i < nHi && naryNumbers[++i] < nPivot);
		while (j > nLo && naryNumbers[--j] > nPivot);
		if (i >= j) break;
		std::swap(naryNumbers[i], naryNumbers[j]);
	}
	std::swap(naryNumbers[nLo], naryNumbers[j]);
	return j;
}

void sort(int naryNumbers[], int nLen) {
	std::random_shuffle(naryNumbers, naryNumbers + nLen);
	sort(naryNumbers, 0, nLen - 1, true);
}

void sort(int naryNumbers[], int nLo, int nHi) {
	if (nLo >= nHi)	 return ;
	int j = partion(naryNumbers, nLo, nHi);
	sort(naryNumbers, nLo, j - 1);
	sort(naryNumbers, j + 1, nHi);
}

Coding Details

  1. Counter-intuitively, we stop scanning at the equal keys in the inner while loop of partition function. Such while (i < nHi && naryNumbers[++i] <= nPivot) statement would make the quick sort quadratic time when sorting numbers with many duplicates. Consider an array of size 10 and each number is the same value say 1, if we do not stop at equal keys, then partition would return the corner index while in our code above, the partition will return the index at the middle. What a big difference!
  2. in while (j > nLo && naryNumbers[–j] > nPivot); j > nLo is actually not necessary because if j is decremented to nLo, then the while loop will terminate, and the following statement if (i >= j) break; will break out the outer while loop.
  3. Why we swap number at nLo and j rather than nLo and i? Why return j not i? This is is not very intuitive because of its trickier (than it might seem) test on whether the pointers cross. Think about this: j must point to the last element which is less than or equal to our pivot number at nLo: if j still pointer to a larger value, then we won’t be able to break out the inner while loop while (j > nLo && naryNumbers[–j] > nPivot);  And j cannot point to any elements before the last one among those which are smaller or equal to our pivot number because once the pointers cross, the while loop break at the statement if (i >= j) break;

Practical Improvements

  1. Do Insertion Sort for small array
  2. Pick median of 3 (random) items as the pivot value rather than always the left most one
  3. Do random shuffling to guarantee the performance
  4. One advantage of Quick Sort is that it is done in-place, extra array could make partitioning easier and stable but it is usually not worth the cost.

Summary

C++ implementation of Quick Sort with counter-intuitive parts (e.g., loop termination,  stop at equal keys) are explained here and common practical improvements are included.


(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com  as well as the original permalink

URL for any reprints,  and please do not use it for commercial purpose)

Written on October 21, 2014