Quick Sort
Description
This algorithm makes multiple passes through the data set.
In the first pass, it uses the first item in the list as a "pivot", and
then it separates all the items into two groups on either side of the
pivot: all the items that are less than the pivot (in no particular
order), then the pivot item, then all the items that are greater than
the pivot (again, in no particular order).
The two groups might be the same size, as in the diagram below, but
they might not be.
| pivot 0 |
group 1: less than pivot 0 |
|
|
group 2: greater than pivot 0 |
|
In the next pass, it applies the same algorithm to each of the groups
created in the previous pass, so we now have 4 groups and 3 pivots.
Again, the groups are not guaranteed to be equal in size, and often
aren't.
This process continues, creating more but smaller groups, until the
groups contain just a single item and do not have to be processed
further.
Animation
The Visual Sort section of
this
page
contains small-scale, step-by-step animations of several sorting
algorithms.
- Choose Quick Sort in the
first drop-down menu.
- Repeatedly click on Step until you
have a sense of how the algorithm works. Then click Run and check whether its continued
behavior is what you expect.
- You can click on the New Sort
button to get a new set of random data if you want to repeat
the process to understand the algorithm better.
Performance
In each pass, this algorithm parcels all items to one side or another
of its current pivot, comparing and swapping roughly N items in each
pass.
(N is the number of data items to sort. For example, N would be 1000 if
the data set contains 1000 items.)
How many passes does it need? Well, if the data start out
sufficiently random, each group is cut roughly in half
in each pass. Ideally, the group sizes go from
1000 to 500, to 250, to 125, to 63, to
32, to 16, to 8, to 4, to 2, to 1, so the number of passes would be
log2(N), also known as lg(N).
The actual performance is likely to be somewhat worse because the groups
do not divide exactly equally.
(The worst case is if the data are
sorted before the process begins; the group sizes go from 1000 to
999, to 998, to 997, etc., requiring N passes.)
Code
void sort(int[] data, int numItems)
{
recSortQ(data, 0, numItems - 1);
}
void recSortQ(int data[], int startRange, int endRange)
{
if ( ( endRange - startRange ) < 1 )
return;
int pivotLoc = pivot(data, startRange, endRange);
recSortQ(data, startRange, pivotLoc - 1);
recSortQ(data, pivotLoc + 1, endRange);
}
int pivot(int data[], int startRange, int endRange)
{
int pivot = data[startRange];
int leftIndex = startRange + 1; // Skip the pivot
int rightIndex = endRange;
while ( leftIndex <= rightIndex )
{
while ( data[leftIndex] <= pivot && leftIndex <= rightIndex)
{
leftIndex++;
}
while ( data[rightIndex] >= pivot && rightIndex >= leftIndex )
{
rightIndex--;
}
if ( leftIndex < rightIndex )
{
int temp = data[leftIndex];
data[leftIndex] = data[rightIndex];
data[rightIndex] = temp;
leftIndex++;
rightIndex--;
}
}
if ( rightIndex > startRange )
{
data[startRange] = data[rightIndex];
data[rightIndex] = pivot;
}
return rightIndex;
}