Quicksort

Quicksort is a popular sorting algorithm. That being the case makes sense that we see how to implement it right? Let’s go then.

This algorithm basis itself on divide-and-conquer. For our purposes what that means is that, at each step we will use a pivot and divide our list into two sublists: one with lower values and one with equal or bigger values. Then we sort each sublist. The stopping condition of our algorithm will be when we reach the empty list. When that happens we start merging the sublists into our final and sorted list. Confused? Let’s see an example.

def quicksort(lst):
    if lst == []:
        return []

    # Partitioning the list. 
    # For the sake of simplicity, we'll use the first element as the pivot.
    lower = quick_sort([x for x in lst[1:] if x < lst[0]])  
    bigger_or_equal = quick_sort([x for x in lst[1:] if x >= lst[0]])

    return lower + [lst[0]] + bigger_or_equal

This example helps clarify the algorithm. As we can see, we start by checking if the list is empty. We don’t want to sort an empty list, now do we? If that’s the case, we return. Good!

Next we divide our list into two parts: lower and bigger or equal using the first list element as the pivot. At the same time we’re recursively applying the quicksort function to each sublist (that will eventually end when the lists are empty). When everything is sorted we merge the sublists and return.

Still we me so far? Excellent! If you’ve read some of my previous posts, you’ve have noticed that I’m a fan of testing. I don’t want you to call me a liar and as such let’s write some tests and check that the algorithm works.

import unittest
from quicksort import quicksort

class TestQuicksort(unittest.TestCase):
    def setUp(self):
        self.list_to_sort = [3,2,5,48,34,23,12]

    def test_quicksort(self):               
        sorted_list = quicksort(self.list_to_sort)
        self.assertEqual(sorted_list, [2, 3, 5, 12, 23, 34, 48])

$ python quicksort_tests.py
.

---

Ran 1 test in 0.000s

OK

It works. Phew! Nice to have some tests to make sure everything works and also if we decided to change something we can run them and check that we haven’t broken anything.

This is all nice but I never said that this algorithm is exclusive for integers, did I? No! Although the idea is all there, it would be nice if our algorithm worked with other types. That being said we will do a small change to our implementation so that we can sort list with other elements types.

Our approach will be to pass a compare function to the algorithm and use it instead of our integers comparisons. Because in Python functions are also objects, we can pass them as arguments to other functions.

But this time we’ll do it the other way around: we will write our tests first and then our code. TDD style!

import unittest
from quicksort import quicksort_gen

class TestQuickSortGen(unittest.TestCase):
    def setUp(self):
        self.list_integers = [3,2,5,48,34,23,12]
        self.list_letters  = ['a', 'r', 'd', 'b']

    def comp_int(self, a, b):
        if a < b:
            return -1
        else:
            return 1

    def comp_letters(self, char1, char2):
        if ord(char1) < ord(char2):
            return -1
        else:
            return 1    

    def test_quicksort_int(self):
        sorted_list = quicksort_gen(self.list_integers, self.comp_int)
        self.assertEqual(sorted_list, [2, 3, 5, 12, 23, 34, 48])

    def test_quicksort_letters(self):
        sorted_list = quicksort_gen(self.list_letters, self.comp_letters)
        self.assertEqual(sorted_list, ['a', 'b', 'd', 'r'])

if __name__ == "__main__":
    unittest.main()

As a convention, the compare function will return -1 if the first element is lower and 1 otherwise.

$ python quicksort_tests.py
FF
======================================================================
FAIL: test_quicksort_int (main.TestQuickSortGen)

---

Traceback (most recent call last):
File “quicksort_tests.py”, line 31, in test_quicksort_int
self.assertEqual(sorted_list, [2, 3, 5, 12, 23, 34, 48])
AssertionError: None != [2, 3, 5, 12, 23, 34, 48]

======================================================================
FAIL: test_quicksort_letters (main.TestQuickSortGen)

---

Traceback (most recent call last):
File “quicksort_tests.py”, line 35, in test_quicksort_letters
self.assertEqual(sorted_list, [‘a’, ‘b’, ’d', ‘r’])
AssertionError: None != [‘a’, ‘b’, ’d', ‘r’]

---

Ran 2 tests in 0.000s

FAILED (failures=2)

With our tests in place (and failing!) we can go ahead, write some code, and make them pass.

def quicksort_gen(lst, comp):
    if lst == [] :
        return []

    # Partitioning the list. 
    # For the sake of simplicity, we'll use the first element as the pivot.
    lower           = quicksort_gen([x for x in lst[1:] if comp(x, lst[0]) == -1], comp)
    bigger_or_equal = quicksort_gen([x for x in lst[1:] if comp(x, lst[0]) == 1], comp)

    return lower + [lst[0]] + bigger_or_equal

The changes to the original code are very small. As previously said, we only replaced our integer comparison function by the function passed as an argument.

Running the tests we no have (drum roll…):

$ python quicksort_tests.py
..

---

Ran 2 tests in 0.000s

OK

Tests passed. Great! Easy, wasn’t it?