Quicksort - Almer S. Tigelaar

Some people put their things in a pile, for example clothes. When they need something they search through that unorganized pile. That approach makes me cringe. I like my things to be organized, whether it comes to groceries, packing my stuff for a holiday, or sorting my own documents into folders: physically or virtually.

There are many situations in daily life where sorting is an important step in a series of actions usually lost in the cloud of our own subconscious competence. For example sorting knives, forks and spoons into a drawer (sorting into buckets) or packing a bag with large items at the bottom and small ones at the top (sorting for a particular ordering).

In this brief article we look at one of the most famous algorithms for sorting things in a particular order: quicksort.

Quicksort Conceptually

Imagine you are standing in a gym. Team selections are about to me made, and everyone there has to stand in line first. Forget about your childhood frustrations about being picked last for a team for now and bear with me. Now that everyone is standing next to each other. The line has to be ordered so that the smallest person in line is way on the left and the tallest person on the right.

If you ask everyone to organize themselves like this. They will look at the people standing next to them and move over positions until they are at the right spot. Let’s imagine that nobody can voluntarily move, until you tell them to, and you can decide only to swap two people. You need to do this until the line is in order. Let’s try it!

Part I: Left and Right

To make this a bit more concrete let’s consider this line with five people (the lengths behind them are in centimeters):

Abe=181 | Beatrice=170 | Carlos=174 | Dana=172 | Edward=179

We first pick a random person, say Carlos, referred to as the pivot. Our goal is to make sure that everyone to the left of Carlos is smaller and everyone to the right of him is taller them him. We do this by finding someone on the left first that is taller than Carlos (and thus needs to be on the right), and someone on the right that is smaller than Carlos (and thus needs to be on the left).

We move from the outside in. Starting on the left with Abe (181), we see that he is taller than Carlos (174). Thus we need to find someone on the right who is smaller than Carlos to trade places with him. Edward (179) is not, so we skip him. However, Dana (172) is smaller, so she can swap with Abe. Let’s do that:

Dana=172 | Beatrice=170 | Carlos=174 | Abe=181 | Edward=179

As a final step we can see that Beatrice (170) is smaller than Carlos, so should be to his left, and thus no more swapping is needed. So, now we have what we wanted: everyone to Carlos’s left is smaller and everyone to his right is taller. However, the line is not yet in order!

Part 2: Recursion

We now stop considering Carlos. Since he is already in the correct position. What we are going to do is to apply the exact same approach as we did before, but to two parts of the entire line. Let’s start with the left part first: consisting of all of those to the left of Carlos.

Dana=172 | Beatrice=170

The left part consists of only Dana and Beatrice. We pick one of them, say Dana. Like we did before we now want everyone smaller than Dana to be one her left, and everyone taller on her right. Since there are only two people, there is only one relevant question: should Beatrice (170) be on Dana’s right (172) right? And indeed she should be, so we swap Beatrice and Dana:

Beatrice=170 | Dana=172

To Carlos’s right, Abe and Edward should similarly be swapped yielding:

Edward=179 | Abe=181

Now, if we look again at the entire line-up we have:

Beatrice=170 | Dana=172 | Carlos=174 | Edward=179 | Abe=181

And voila the people in line are sorted in order from shortest to tallest. In total we swapped three times: first Dana and Abe, then Beatrice and Dana and finally Edward and Abe.

We conceptually mastered the quicksort algorithm. Which is all about sorting things that need to be ordered with as few swaps as possible. How did this way of sorting come about? To answer that we must go back to 1959.

History of Quicksort

Charles Antony Richard (C.A.R.) Hoare was born in Sri Lanka to British parents in 1934. Being a rather studious child everyone referred to him as a “Professor”. His real childhood wish was to become a writer. Drawn into computer science from a related interest in mathematical logic, he got started programming on punch cards and paper tape in the late fifties.

Hoare studied modern military Russian during his mandatory service in the Royal Navy. As a graduate student he spent some time in Moscow. There he wrote a scientific paper, in Russian, on Machine Translation.

Translating from Russian to English using a machine was no panacea. Alphabetically sorted dictionaries were stored on slow magnetic tapes. Making a pass over such a tape, from start to finish, was slow and time consuming. Hence, doing so for each individual word in a sentence to translate would take a very long time.

Hoare figured that a single pass over the tape would be much faster. However, that required one to sort the sentence to be translated, so that the words would be in alphabetical order (for example: “a wonderful colorful day” in alphabetical order becomes “a colorful day wonderful”). He first started thinking of this naively, coming up with what we now know as bubble sort. An obvious algorithm that most people come up when first confronted with the problem “sort this list of things in order”.

He realized though that bubble sort would be far too slow. Hence, he came up with quicksort as his second approach. An exercise in programming, that he later referred to as the only really interesting algorithm that he ever developed. He later greatly influenced the design of early programming languages, made landmark conceptual contributions to computer operating systems, and the formal verification of computer programs. But, for now: back to quicksort.

The Quicksort Algorithm

Quicksort has several nice properties, namely: it does not require extra space beyond the items to be sorted. We swapped everyone on the line without using extra space in the gym. This is referred to as ‘in-place’ sorting. It also has good average case complexity (which means: it is efficient, even on large inputs it won’t take too long).

Here is a short implementation in Python that sorts our example input according to the quicksort algorithm. Just the lengths are used as input here, the names of the people in line are not included.

def quicksort(line, left, right):
    if left < right:
        pivot_index = partition(line, left, right)
        quicksort(line, left, pivot_index)
        quicksort(line, pivot_index + 1, right)
    return line

def partition(line, left, right):
    # Pick the middle element as pivot	pivot = line[(left + right) // 2]
    i = left
    j = right
    while True:
        # Find the lowest element on the left	
        while line[i] < pivot:
             i += 1
        # Find the highest element on the right
        while line[j] > pivot:
             j -= 1
        # Stop if they're equal
        if i >= j:
             return j
        # Swap them
        k = line[i]
        line[i] = line[j]
        line[j] = k

gym_line = [181, 170, 174, 172, 179]
quicksort(gym_line, 0, len(gym_line) - 1)
print(gym_line)

Conclusion

Sorting is something we do everyday, but it’s not something we are often aware of. Quicksort is one, of many, sorting algorithms out there used in practical applications. If you have ever sorted a spreadsheet, some emails or any other data, you have almost certainly have used it directly, and there are countless other places where its usage is not directly apparent, but it’s certainly there.