QuickSort(list, start, end):
if start >= end:
return list // size 0/1 already sorted
else:
pivotLocation = Partition(list)
QuickSort(0 to pivotLocation - 1) // Sort the first half
QuickSort(pivotLocation to end) // Sort the second half
Here, most of the interesting work happens during the partition step, where the list is divided into two parts. This section focuses on that partitioning process. The goal of partitioning is to pick a pivot element and rearrange the list so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
There are multiple partition algorithms, we will focus on the one known as the Hoare partition scheme. The basic strategy of this algorithm is to create an index that starts at the begining of the range being partitioned (i) and an index that starts at the end of the range being partitioned (j). These two indexes are used to scan the list from both ends towards the middle, swapping elements to ensure that elements less than the pivot end up on the left, and elements greater than the pivot end up on the right.
pivot = list.at(start)
i = start + 1
j = end
while i ≤ j:
Move i right until an element ≥ pivot is found
Move j left until an element ≤ pivot is found
if i ≤ j:
swap(list.at(i), list.at(j))
// Done swapping pairs - place pivot in its final position
swap(list.at(start), list.at(j))
Use that pseudocode and the interactive below to practice partitioning a list. Use the instructions in the interactive for guidance.
While i ≤ j:
Move i right until i finds a value >= pivot
Move j left until j finds a value <= pivot
if i ≤ j: // if Indexes have not crossed
// swap the values at i and j
swap(list.at(i), list.at(j))
Finish by swapping the pivot with the value at j
Real world implementations often select the pivot using a more sophisticated method than “the first element in the partition range”. We will discuss those in the next section.
Analyzing the partition algorithm is a little tricky because of the nested loops. Normally, nested loops suggest a quadratic time complexity, but in this case, the inner loops do not run independently for each iteration of the outer loop. Instead, the inner loops collectively scan through the list only once.
while (i <= j) {
if (i <= end && vec.at(i) <= pivotValue) {
i++;
}
if (j >= start && vec.at(j) > pivotValue) {
j--;
}
// Swap items at i and j if i < j
if (i < j && vec.at(i) > pivotValue && vec.at(j) <= pivotValue) {
swap(vec.at(i), vec.at(j));
// advance i and retreat j since those items are fixed
i++;
j--;
}
}
It swaps the inner loops for conditional checks. Each iteration of the loop moves either i, or j, or both closer to the other. The size \(n\) of the vector segment being partitioned is determined by the distance between start and end. Those values also are used to set i and j. So the loop describes iterating over \(n\) items.
The same total amount of work will be done when the ifs are turned into whiles. In the version with nested loops, each time an inner i or j loop advance more than once it also reduces the number of iterations left for the outer loop.
