Testing quicksort
published: Tue, 2-Dec-2003 | updated: Thu, 27-Oct-2005
When I wrote my book, I stated in the chapter on sorts that quicksort was extremely rapid, but suffered from being difficult to code correctly. I warned against tinkering with the basic algorithm, especially with the inner loops.
A quick recap: at its heart, quicksort is a very simple algorithm. You select a special element (called the pivot) and arrange the elements of the array you're sorting so that all the elements that are less than the pivot appear on its left, and all those that are greater on its right (this operation is known as partitioning. You then recurse using the same algorithm with the subarray to pivot's left and with the subarray to its right. The pivot itself is in its correct position in the sorted array. Eventually, of course you'll get to a subarray that has just one element, and, guess what?, that's already sorted.
So, quicksort is an example of a divide and conquer algorithm: you restate the problem in terms of a smaller input, with the solution being really obvious for the smallest input of all, and reconstitute it afterwards.
The quicksort problem boils down to two separate problems, then: selecting the pivot element, and partitioning the elements.
For now, the first problem is solved by using the middle element of the array (or the subarray). There are other, more complex, solutions, but this will do for now.
The fun part is the partitioning process. This is where quicksort's famous fast inner loops come into play. Starting at the right, walk left comparing elements to the pivot until we find one that is less than or equal to the pivot. Once we find one (and I'll come to why we always will in a moment), we start at the left and walk right comparing elements until we find one that is greater than or equal to the pivot (and again we always will). We'll end up with two outcomes: the left hand index is still less than the right hand index, or they've met or crossed over (so the left hand index is greater than the right hand index).
For the former case, we will swap over the two elements since they are both in the wrong place. Then we continue with the same process, search from the right, search from the left. For the latter case, we've finished partitioning this subarray and now we need to quicksort the two parts.
Now the problem: how do we know, in walking from the left and from the right, that we won't fall off the end of the subarray we're partitioning? In other words, how do we ensure against the boundary condition?
Essentially, it's the pivot that will stop us and the fact that it's in the middle. Suppose that the pivot is so well chosen that the array we're partitioning is already partitioned. In this case, both the left and right indexes will end up at the pivot element, and we're done. Next case: the right index finds an element less than or equal to the pivot, and the left index does too. We do the swap. Notice something about the swap, though: it puts an element that is less than or equal to the pivot to the left of right index, and it puts an element that is greater than or equal to the pivot to the right of the left index. In other words, if we swap at least once, we're putting elements into positions that will stop the leftward march of the right index and the rightward march of the left index. Since we've already shown that if there is no swap at all the pivot element will stop the indexes, we've shown that we don't have to explicitly code for the boundary condition: selecting the middle element as pivot will solve the problem for us.
(Note that a lack of attention to this important point means that the quicksort listed in Rod Stephen's book Ready to Run Delphi 3.0 Algorithms, as well as the Visual Basic version, is too slow. He coded both fast inner loops to check for running off the end of the array. This saps both inner loops like you wouldn't believe: instead of a comparison and an index increment/decrement, we get two comparisons and an increment/decrement per cycle through the loop.)
Notice that the pivot is not guaranteed to split the array into two exact halves. All we're trying to do is to move the elements less than the pivot to its left and those greater than to its right. It may well be that there are no elements less than the pivot, for example, in which case the partitioning really didn't do very much. This, by the way, is the reason why quicksort can degenerate into a slow sort: we manage to choose the worst possible pivot every time so that the partitioning process produces two subarrays, one with a single element, the second with all the others.
Having read this description, you're sure to understand the following code in Delphi that sorts an array of integers.
procedure QSIntegers(var A : array of integer;
aFirst : integer;
aLast : integer);
var
L, R : integer;
Pivot : integer;
Temp : integer;
begin
{while there are at least two items to sort}
while (aFirst < aLast) do begin
{the pivot is the middle item}
Pivot := A[(aFirst+aLast) div 2];
{set indexes and partition}
L := pred(aFirst);
R := succ(aLast);
while true do begin
repeat dec(R); until (A[R] <= Pivot);
repeat inc(L); until (A[L] >= Pivot);
if (L >= R) then Break;
Temp := A[L];
A[L] := A[R];
A[R] := Temp;
end;
{quicksort the first subfile}
if (aFirst < R) then
QSIntegers(A, aFirst, R);
{quicksort the second subfile - recursion removal}
aFirst := succ(R);
end;
end;
procedure QuicksortIntegers(var A : array of integer);
begin
QSIntegers(A, 0, length(A) - 1);
end;
So, back to my original exhortation: tinker with care. Just recently I had an email correspondence with someone who was trying to add sorting to his array-like string collection class. For one reason or another, he tinkered with the algorithm I've just presented in his implementation (I'm guessing it was for speed reasons given the application for strings). In doing so, he broke the algorithm, and I got the email saying that my algorithm was wrong. (My algorithm? Er, not so, quicksort was invented by C.A.R.Hoare in 1960: I was 3 at the time.) In fact, he'd tried to implement it twice, and both times the implementation was wrong. He was contrite about the fact my algorithm was broken, and even sent me his code that generated two million lines of text to sort.
I took a look at his code. It was pretty obvious what the problem was. Instead of saving the value of the pivot element, he was saving the index of it. The assumption he was therefore making was that the pivot element wouldn't change position, whereas, as we've already seen, it's not guaranteed that it will end up in the middle of the elements at all.
So, that's what I replied, although I also provided some example data that illustrated the problem I was describing. Instead of 2 million items, I provided five.
What can be learnt from this small episode? First, understand the algorithm you are trying to implement. My correspondent didn't, and therefore couldn't see why his implementation was failing. Second, it is pointless using a data set of two million items to test an implementation. Yes, it's kind of fun seeing so many items being sorted, but in the end if the two million items didn't get sorted, you have one heck of a job ahead of you trying to work out why. (Consider this: the recursive quicksort routine will be called about two million times. Which one of those two million calls is causing the bug? Rather you than me. By the way, one way to optimize quicksort is to reduce the number of these recursive calls.) Third, instead of relying on a large number of items in your data set testing all paths through your implementation, write small, very focused tests that check individual paths. With small tests it's fairly easy to devise a particular sequence of items to check your code. If the test fails, it's usually very simple to deskcheck (and/or debug) and discover the problem.
So which tests would I use to test the quicksort routines above? First is easy: one item (there's nothing to do!). Second: two items in order, and third: two items out of order. Fourth (a little trickier): two items, both the same. This set of tests caters for the initial conditional call in the recursive quicksort routine. Now, we get into the more interesting stuff.
The next set of tests: a complete set of three-item tests. All permutations of three different items. All permutations of two different items (both with the repeated item less than the other, and greater than the other). All three items equal.
You might think that this was enough. But, actually, no. If I change the last non-trivial statement in the QSIntegers routine above to "aFirst := succ(L);", the tests don't fail. In other words, there needs to be enough items to force the loop to have to partition at least three items.
We'll separate out the remaining tests to operate on five items. The first larger test then is a set of items in already sorted order, 12345. This test ensures that the routine works, even it we do not have to do any swaps. The next is to arrange the items in reverse order, 54321. This forces every cycle of the first call to the quicksort routine to swap items (for other calls the items will already be sorted). The next sequence is to force the pivot to be the smallest item in the list, 54123, the next one, the largest, 14523. Both of these tests will partition the set into a one item subset and another subset containing everything else. (And in fact it is the first of these latter tests that will fail with the fake bug.) A final test is to make all the items equal. This will ensure that we cope with lots of items being equal to the pivot.
All these tests ensure that we run through (pretty well) all possibilities of the paths through the recursive routine. I suppose we could, if we really wanted to, write a test that would test all permutations of 5 items, but looking at the coverage of these tests, I think we're pretty safe. Note, by the way, that this is often what happens in "real life". You test all the combinations you think are meaningful since you can't test them all. And you hope that you've thoroughly tested the routine, or class, or unit. Sometimes you won't have, but when the bug finally rears its head, you'll (hopefully) have a reproducible test case that you can write as a unit test and ensure that the bug never happens again. Sometimes the test case will point to other unit tests you should write, maybe obviating other tests from happening.
(Download source for this article.)
