Roger Ngo's Website

Personal thoughts about life and tech written down.

Quicksort

Really, now?

Quicksort is one of those sorting algorithms that we learn pretty early in our Computer Science careers and is something we come to conceptually understand, but oftentimes, forget how to implement it. It really is useful to understand the implementation as Quicksort does bring some challenges in consideration of performance based on certain characteristics on how one initially approaches the problem (pivot element selection), how the data set is already arranged (mostly sorted, or randomized placement?). Not only that, but there are many gotchas that could happen such as off-by-one errors, or falling into infinite loops.

Overall, the Quicksort algorithm is a fun programming exercise to do when implementing it. Here are some of the little exercises that Quicksort ultimately end up flexing your programming muscles:

  • Bounds checking. Do you have the right boundary conditions met?
  • Recursion. Quicksort is often implemented recursively.
  • Looping. Quicksort's comparison is made through the use of a loop. First, comparison an element on one side (left side) against another element on the opposite side (right) based off of a reference element (pivot).
  • Temporary variables and swapping. Ask any beginner how to swap two elements in an array, you'd be surprised!
  • Array manipulation.

The Basic Algorithm

Each call to Quicksort must fullfil the following condition:

All elements of the left partition of the current subset of elements to be sorted must be less than all the elements of the right partition of the subset to be sorted. The partition is divided by a reference element, the pivot.

The subset is defined by the sub-array which is constrained by a given low and high index of our current recursive function call.

If you were to ask specifically to me: What makes something like Quicksort so difficult? My answer would be something on the lines of: The difficulty is going to be the algorithm involving making the appropriate recursive calls and keeping track of these calls in a mental stack (the implicit stack that gets created during function calls). This is not too bad once we have the main approach of the algorithm understood.

The main algorithm:

  1. Our sort function should take the following parameters:
    • The array to be sorted. We can refer to this as the current subset.
    • The start index of the current subset.
    • The end index of the current subset.
  2. Define the base case. The base case is needed to stop the recursive calls. The appropriate base case of such an algorithm involving this type of sorting is when our start index is greater than our end index. When such a condition happens, it means that our start index of our current subset has overlapped with the end index of the same subset. We run into this condition when we have run out of elements to swap with. It is important to get this base case correct as it is required to terminate the recursive calls.
  3. Select the pivot element. The pivot element is going to be the reference element in which we will determine whether a swap of any other element will fall into the left or right side of the current set. Elements falling into the left side of our set will be elements less than our pivot element, while the right side will be elements greater than our pivot element.
  4. Define two pointers to track the left and right side. The first pointer which we will refer to as i, will be the current element on the left side of our set to be compared. The second pointer, j will be the current element on the right side of our set to be compared.
  5. Loop indefinitely until the left index is greater than our right index. This means the pointers have crossed each other and the list of elements satisfy the condition in that all elements prior to the pivot element is less than the element itself, and every value succeeding the pivot element is greater than the element itself. Remember, this does not mean the sorting is done. It just means that we run into the condition that left < right.
  6. Starting at location i, compare the current element at i with the pivot element. If the element is less than the pivot value, increment the index at i until the element at i is less than the pivot value. Remember, always check set boundaries to not fall off the array/set in which we are processing.
  7. Starting at location j, compare the current element at j with the pivot element. If the element is greater than the pivot value, decrement the index at j until the element at j is greater than the pivot value. Remember, always check set boundaries to not fall off the array/set in which we are processing.
  8. If the pointers have overlapped, that is, i > j, then terminate the routine. The data set has all the elements in a valid position.
  9. If the pointers have not overlapped, that is, i < j, then swap the elements pointed at i and j.
  10. Finally, swap the pivot element at the end of the array to the final position pointed by i.
  11. Recursively call this sort routine against the two sides. First, going from the start index to (i - 1), then from (i + 1) to the current end index. We do not touch the position at i as it is implicitly in its final position.

Although Quicksort is an O(N logN) algorithm, it is really dependent on the pivot index you choose to perform the algorithm. A bad pivot index can result in a run time that may be even worse than O(N logN).

For example, suppose have have picked a pivot which is either the smallest value, or the largest value in our set. This causes the pivot to end up in being at either boundaries of the array. This causes all elements to be shifted before or after the pivot element recursively. In effect, this turns into a quadratic runtime O(N^2).

There are several strategies in determining a good pivot index. Things such as shuffling the array and randomizing the locations of every elements before processing will help in not picking a bad pivot. Another way is to take a median of 3 elements and pick the closest value to that.

For simplicity, and for sake of example, let's just choose the pivot to be at the mid point of the data set:

int mid_point = low + (high - low) / 2;

Implementation

Let's define the method signature:

public void sort(int[] data, int start, int end);

Our function takes in:

  • The total array data set.
  • The current start index of the array subset to be sorted.
  • The current end index of the array subset to be sorted.

The key here is to treat our array being passed in as a subset, or a subarray based off of the start and end indices. Although we receive the total data set, we are essentially only sorting elements lying within our current subarray from start to end.

As with every recursive algorithm, we need to first think about the termination case, or base case to stop any infinite recursive calls.

if(start > end) {
    return;
}

Now, lets find the pivot index. For this implementation, the mid point formula will be sufficient:

int pivotIdx = start + (end - start) / 2;

We can now use this pivot index to swap with our last element in our current working window.

int pivot = data[pivotIdx];
data[pivotIdx] = data[end];
data[end] = pivot;
    

We define variables i and j as the current left and right indices to be compared against the pivot element.

int i = start;
int j = end - 1;
    

Notice how we defined j to start at the element preceding the end index of our array? It is because the pivot element is the value in which we want to compare against and we do not want to end up swapping this during our sorting operation.

Now, taking a look at the heart of our sorting algorithm, an outer loop is defined to be run infinitely, but only broken out when i overlaps with j. In this loop, we'll compare the current element pointed by i against the current element pointed by j and swap the values if they are not in the correct order.

If we are sorting in ascending order, the left value must always be less than the right value.

while(true) {
    while(i < data.length && data[i] < pivot) {
        i++;
    }
    while(j >= 0 && data[j] > pivot) {
        j--;
    }
    if(i >= j) {
        break;
    }
    else {
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
}

Once the i and j pointers have overlapped, we have fulfilled the condition that all elements left of our pivot in our subarray is less than the pivot value, and all elements to the right of our pivot are greater than the pivot value. We will then swap the pivot back, but now in the location where i pointer left off:

// swap back
data[high] = data[i];
data[i] = pivot;

And of course, we will need to sort the sub arrays. We can do so by recursively calling the sort routine on the left side of the current array (start, i - 1) and the right side of the array (i + 1, end).

sort(data, start, i - 1);
sort(data, i + 1, end);

Eventually, our sort routine will stop calling itself recursively due to two things happening:

  • The elements are sorted, therefore the left index will always cross with the right index in our sorting loop. This causs a break in the loop and makes the next recursive call with an even smaller window of data points to be sorted.
  • When the above happens, we will eventually hit our base case, which starts the frames of our function calls to pop off our implicit stack.

Tracing an Example

To get a visual idea on how Quicksort runs, let's take a step back and do a trace on a test case. Let's say we have an unsorted array of integers:

int[] data = {13, 9, 1, 3, 7, 5, 2, 9, 6, 8, 2};

Our function call will then be:

sort(data, 0, data.length - 1);

Since start = 0 (0), and end = data.length -1 (10), our base case is not true, so we will begin calculating the pivot index along with recursively sorting the array window from index 0 to 10 (which is the whole array). For this example, we will simply use the mid point to find the pivot index.

int pivotIdx = 0 + (10 - 0) / 2;

Our pivot index is then 5.

13, 9, 1, 3, 7, 5, 2, 9, 6, 8, 2

Now, we'll do a swap between our pivot and last element in our array:

13, 9, 1, 3, 7, 5, 2, 9, 6, 8, 2
13, 9, 1, 3, 7, 5, 2, 9, 6, 8, 2
13, 9, 1, 3, 7, 2, 2, 9, 6, 8, 5

From here, we'll define i to start at index 0 and j to start at index 9.

13, 9, 1, 3, 7, 2, 2, 9, 6, 8, 5

With our looping logic, we'll just compare 13 against 5, our pivot value. We see that 13 is greater than 5, so we do not increment i. i is at 0. For the next inner loop, we'll compare 8 against 5, and we'll see that 8 is greater than 5. We decrement the position at j. As we execute this loop, we also find that 6 and 9 are also greater than 5, but when the current element pointed by j is now 2, we will break the loop because the condition in that j is greater than the pivot element is no longer true. Therefore, our array now looks like this:

13, 9, 1, 3, 7, 2, 2, 9, 6, 8, 5

Now, we will swap elements 13 and 2, leading us to this array:

2, 9, 1, 3, 7, 2, 13, 9, 6, 8, 5

Since our lop runs infinitely, we're back at moving the i pointer. Since the element pointed by i is now less than the pivot element, we'll increment i, which now points to 9,

2, 9, 1, 3, 7, 2, 13, 9, 6, 8, 5

Similar to the last iteration, we'll now start decrementing j. Doing so stops us at 2.

2, 9, 1, 3, 7, 2, 13, 9, 6, 8, 5

Now we'll do another swap.

2, 2, 1, 3, 7, 9, 13, 9, 6, 8, 5

Continuing on, we'll move i and j until we need to swap again. We'll notice one thing: The i and j pointers collide and overlap! When this happens, we'll break out of the loop. Our array then looks like this:

2, 2, 1, 3, 7, 9, 13, 9, 6, 8, 5

We now know that the final position for this recursive call for i is now at 4. So we'll swap it back with the pivot.

2, 2, 1, 3, 5, 9, 13, 9, 6, 8, 7

Now, we'll recursively call the sort routine on left and right sides. The left side starts at the lowest point (0) to just where i begins (3), and the right side goes from 5 to the highest point (10).

2, 2, 1, 3, 5, 9, 13, 9, 6, 8, 7

As you can see from above, the pivot is now at its final position. We'll do this recursively until we have a sorted array. (Sort 0->4, then sort that half from 0->i-1, i+1, 4, etc.)

Full Implementation

public void sort(int[] data, int start, int end) {
    if(start > end) {
        return;
    }

    int pivotIdx = start + (end - start) / 2;
    int pivot = data[pivotIdx];
    data[pivotIdx] = data[end];
    data[end] = pivot;

    int i = start;
    int j= end - 1;
    while(true) {
        while(i < data.length && data[i] < pivot) { i++; }
        while(j >= 0 && data[j] > pivot) { j--; }
            
        if(i >= j) {
            break;
        }
        else {
            int t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    }
            
    data[end] = data[i];
    data[i] = pivot;
            
    sort(data, start, i - 1);
    sort(data, i + 1, end);
}

Tips

To understand this algorithm better, I personally had to:

  • Trace each call for several cases of arrays differing in size.
  • Fire up the debugger whenever something went wrong such as: stack overflow, array index out of bounds, a sort call only running once, etc.

Also lots of patience was involved in my initial study because I easily forgot about taking into consideration of the left/right sides running out of bounds of the array.

Quicksort is hard to get right. I would be lying if I said that I could implement it perfectly by heart. The fact for me is that I regularly need to reference the algorithm and think about it for a bit before being able to code it. I believe that's ok. :)