Home > Code Dump > Code Dump: Quicksort in Python

Code Dump: Quicksort in Python

Okay, I’m sick of this only-posting-three-days-a-week crap. So Tuesdays are going to be my code dump. Whatever I’ve been writing will go up here, hopefully well commented and clear. If I haven’t written anything, I’ll dig deep in my directory of old crusty code and pull out something interesting I’ve written in the past. If I run out of that, I’m going to turn in my badge & gun and take a job sweeping supermarkets.

To start off, an implementation of quicksort written in Python.

I decided on quicksort on the advice of Randall Muroe:

Which sorting algorithms should I use? They taught me so many.

This is tricky. Most of what they teach you in school is just as an example of how to think about algorithms; 99% of the time you shouldn’t worry about optimizing your sorts. Just learn to implement Quicksort (which is very good) and use that without fretting about it too much. People overfocus on efficiency over clarity and simplicity. And most of the time the environment you’re coding in will have an efficient sort function built-in anyway.

Note: If you’re interviewing for a company for a position with a focus on algorithms, the above is not an excuse not to know your stuff.

Quicksort is, per Wikipedia, a variably-stable comparison sort. Variably-stable is a term I just made up because I needed something to encapsulate the fact that the general form of quicksort doesn’t specify whether its a stable sort or not. What’s a stable sort? Well, let’s say you’re sorting a list of ordered pairs, in this case [[2, 5], [1,2], [4, 3], [2,3]] by their first number. So, it’s really a problem of sorting [2, 1, 4, 2]. But the two different 2 elements are not equivalent. You could either apply sorting rules to those as well, which would result in [[1,2], [2,3], [2,5], [4,3]]; on the other hand, you could preserve the order of the elements from the source list, which would result in [[1,2], [2,5], [2,3], [4,2]].

The latter method of leaving original order intact is an example of stable sort, which is a sort that leaves “equivalent” elements in their original sorting. It’s not immediately clear to me the uses of being a stable sort, since it can mean that sometimes you’ll end up with data that is “out of order”, but I’m sure there’s some reason.

Moving on, the way quicksort works is actually easier to understand than the stable algorithm crap. Well, that is, if you understand recursion. Recursion is one of those things in computer science relies on the “man’s mind, once stretched by a new idea, never regains its original dimensions” concept. Once you get it, you’ll see how to use it everywhere, even if it’s terribly inefficient.

See, recursion is the process of calling a function from within itself. For example, in quicksort, you break up the list to be sorted into three smaller lists, and then run a quicksort on those. Each of those three is then broken into a separate three, and so on until you end up with a list of either one or zero entries. Your function will attempt to quicksort those, but quicksort will just laugh and spit the one item list back out. “It’s already sorted, moron!”

So, some nicely numbered steps.

  1. Make three lists, lessThan, greaterThan, and equal.
  2. Pick an item in the list and assign it to pivot. It doesn’t really matter which element it is, so you can just take the first or last element, whichever you like more. This saves you a few CPU cycles from picking a random element in the list, which doesn’t gain you anything. Anyways, if your data is really in need of sorting, this will effectively be a random selection.
  3. Check each item in the list against the pivot and sort into one of the three lists, lessThan, greaterThan, & equal, depending on its relative value.
  4. Run quicksort on each of lessThan and greaterThan, giving back a result of (sorted) lessThan plus equal plus (sorted) greaterThan.
  5. If quicksort is ever called on a list of length 1 or 0, return the list immediately instead of running through this whole process.

What follows is the program code. However, I wholly underestimated the difficulty of the WordPress publishing system for something as simple as indented code. Not only is the <code> tag useless because it only lasts until the next line break (and is an in-line element by default), but WordPress strips out all user defined white space. It my editing window, all of the indented blocks (which are essential to Python) display fine. But how to represent this on the actual display page is beyond me.

At this point I’m too frustrated dealing with this absurd system to even try and provide examples. The code works, but it seems that WordPress is determined to keep that only to me.

A benefactor points out the <pre> tag, which I believe stands for “pre-formatted text”. The funny thing is, I would expect the below code, which is rendered with such a tag, to get the same functionality out of the <code> tag. Oh well, problem solved.

#Quicksort implementation for educational purposes
#31 March 2008

#Works on any list of anything, so long as each item has valid  comparisons
#with each other item. This is unlike this Java implementation I'm writing in
#parallel which is going to suck because of the lack of duck typing

#Quicksort works by picking one element, and slicing up the list around that "pivot"
#It uses three lists: one each of elements less than, equal to, and greater than
#the pivot element. Then the lesser and greater are themselves quicksorted,
#recursively, and concatenated with the equal to
def quicksort(inlist):
#Our three lists
    less, equal, greater = [],[],[]

    #Recursive base case. If there's nothin' to sort, don't sort nothin'
    if len(inlist) <= 1:
        return inlist

    #Take a pivot. This takes the last element in the list.
    #It really doesn't matter which element it is. Static selection saves execution
    #time to generate a random index. I guess it could be the first element as
    #easily as the last, but this is the way the psuedocode did it, and... yeah.
    pivot = inlist[-1]

    #Go through the whole list and divvy it up into the three sublists
    for i in inlist:
        if i < pivot:
            less.append(i)
        elif i > pivot:
            greater.append(i)
        elif i == pivot:
            equal.append(i)

    #Concats the three lists
    #Since .extend() returns a NoneType, it has to be done in separate statements
    ret = quicksort(less)
    ret.extend(equal)
    ret.extend(quicksort(greater))
    return ret
Advertisements
Categories: Code Dump
  1. March 14, 2009 at 8:53 am

    This is the first time I commented here and I should say that you share us genuine, and quality information for other bloggers! Great job.
    p.s. You have a very good template . Where did you find it?

  1. April 1, 2008 at 5:52 pm
  2. April 8, 2008 at 2:29 pm
  3. May 19, 2008 at 2:01 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: