Implementing Quicksort

Quicksort works by picking a pivot value, then splitting the full list into two sub-lists. The first sub-list has all the values less than or equal to the pivot, and the second sub-list has all the values greater than the pivot. The quicksort function recursively calls itself to sort these sublists, and then to sort the sublists of those sub-lists, until the full list is sorted.

Now it's time to actually implement this in code.

import sys
from load import load_numbers

numbers = load_numbers(sys.argv[1])

# We already have the base case written. Any list passed in that consists of 
# zero or one values will be returned as-is, because there's nothing to sort.
def quicksort(values):
  if len(values) <= 1:
    return values
  # Now we need to create a list that will hold all the values less than the
  # pivot. That list will be empty at first.
  less_than_pivot = []
  # We do the same for values greater than the pivot.
  greater_than_pivot = []
  # Next we need to choose the pivot value. For now, we just grab the first
  # item from the list.
  pivot = values[0]
  # Then we loop through all the items in the list following the pivot.
  for value in values[1:]:
    # We check to see whether the current value is less than or equal to the
    # pivot.
    if value <= pivot:
      # If it is, we copy it to the sub-list of values less than the pivot.
      less_than_pivot.append(value)
    # Otherwise, the current value must be greater than the pivot...
    else:
      # So we copy it to the other list.
      greater_than_pivot.append(value)
  # This last line is where the recursive magic happens. We call quicksort
  # recursively on the sub-list that's less than the pivot. We do the same
  # for the sub-list that's greater than the pivot. Those two calls will
  # return sorted lists, so we combine the sorted values less than the pivot,
  # the pivot itself, and the sorted values greater than the pivot. That
  # gives us a complete, sorted list, which we return.
  return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)

sorted_numbers = quicksort(numbers)
print(sorted_numbers)

Now, in your numbers subdirectory, save the following to a file named 8.txt:

4
6
3
2
9
7
3
5

And run this command in your terminal:

python quicksort.py numbers/8.txt

It outputs our sorted list!

[2, 3, 3, 4, 5, 6, 7, 9]

I don't know about you, but this whole thing still seems a little too magical to me. Let's add a couple print statements to the program so we can see what it's doing.

First, we'll add a print statement right before the first call to the quicksort function, so we can see the unsorted list:

print(numbers)

We'll also add a print within the quicksort function right before the recursive calls. Again, this string formatting code is just to keep the info aligned in columns.

print("%15s %1s %-15s" % (less_than_pivot, pivot, greater_than_pivot))

Let's try running this again:

python quicksort.py numbers/8.txt
[4, 6, 2, 3, 9, 7, 3, 5]
      [2, 3, 3] 4 [6, 9, 7, 5]   
             [] 2 [3, 3]         
            [3] 3 []             
            [5] 6 [9, 7]         
            [7] 9 []             
[2, 3, 3, 4, 5, 6, 7, 9]

• Each time quicksort goes to call itself recursively, it prints out the pivot, as well as the sublist of items less than or equal to the pivot (if any), and the sublist of items greater than the pivot (if any).
• You can see that first it sorts the sublist of items less than the pivot at the top level: [2, 3, 3].
  • It goes through a couple levels of recursion to do that.
  • There are actually additional levels of recursion, but they're from calls to quicksort with a list of zero or one elements, and those calls return before theprint` statement is reached.
• Then it starts sorting the second sub-list from the top level with items greater than the original pivot: [6, 9, 7, 5].
  • You can see a couple levels of recursion for that sort as well.
• Finally, when both sub-lists are recursively sorted, the original call to the quicksort function returns, and we get the sorted list back.

What we've shown you here is just one way to implement Quicksort. Although the basic algorithm is always the same, the details can vary, like how you pick the pivot. Here are just a couple strategies:

• Randomly pick an item from the list passed to the quicksort function to use as the pivot.
• Pick several items, average them, and use the item that's closest to the average as the pivot.

Troubleshooting

If you try running this on a file with thousands of repeated values, it's possible you'll get a RuntimeError: maximum recursion depth exceeded error. This is because Python is set up to prevent functions from calling themselves recursively too many times. Although it's generally not a good idea to disable this behavior, it should be OK while you're just experimenting. You can allow additional recursive calls by adding this line after the import statements in quicksort.py:

sys.setrecursionlimit(10000)