Quicksort

I finally understand the quicksort algorithm. Python helped me with this. Here's how it works:

import random

def quicksort(lst):
    """quicksort
    """
    n = len(lst)
     
    # if the list has 1 or no elements
    if n < 2:
        return lst
     
    # remove a random element and make it the pivot value
    pivot = lst.pop(random.randint(0, n - 1))
     
    # elements less than pivot
    less = filter(lambda x: x < pivot, lst)
     
    # elements not less than pivot
    greater = filter(lambda x: not x < pivot, lst)
     
    # recursively sort the items
    return quicksort(less) + [pivot] + quicksort(greater)
 
if __name__ == '__main__':
    lst = range(10)
    random.shuffle(lst)
    print 'unsorted: {lst}'.format(lst=lst)
    print 'sorted: {lst}'.format(lst=quicksort(lst))

This is the algorithm implemented in Python using recursion. With recursion it is important to identify a base case to avoid infinite loops and stack overflows. In this case our base case is 1 or fewer elements because both a list of 1 element and the empty list are both already sorted.

Now, if you uncomment the print statement and run the code you can see how it works.

Step 1:

Pick a random element from the input list. Let lst = [9, 4, 2, 8, 7, 6, 5, 3, 1, 10], let pivot = 5.

Step 2:

Partition all of the elements less than pivot into a list less. Do the same for the elements that are greater than pivot and call it greater.

Example:

less = [4, 2, 3, 1], greater = [9, 8, 7, 6, 10]

This results in the function returning quicksort([4, 2, 3, 1]) + [5] + quicksort([9, 8, 7, 6, 10])

So now we have [..., 5, ...]

Step 3:

Repeat steps 1 and 2 until you reach your base case, that is, there is either 0 or 1 elements in less and greater

Continuing the previous example:

The next iteration of the recursive call results in quicksort([]) + [1] + quicksort([4, 2, 3]).

Now we have [1, ..., 5, ... ]

Next iteration gives quicksort([]) + [2] + quicksort([4, 3])

The updated list is: [1, 2, ..., 5, ...]

Next iteration: quicksort([]) + [3] + quicksort([4])

Updated list: [1, 2, 3, 4, 5, ....]

Great! We've sorted half the list. Now going to the greater half...

Next iteration: quicksort([8, 7, 6]) + [9] + quicksort([10])

Updated list: [1, 2, 3, 4, 5, ..., 9, 10]

Next iteration: quicksort([]) + [6] + quicksort([8, 7])

Updated list: [1, 2, 3, 4, 5, 6, ..., 9, 10]

Next iteration: quicksort([]) + [7] + quicksort([8])

Updated list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Whoo hoo! We've sorted this (rather boring) list! I hope this has been informative.