« Python and MySQL
Power of the Python FOR loop »

Python Quicksort

Here is simple quick sort function written in Python to sort a list of numbers.

def qsort(toSort):

# return the list if only one is left
if len(toSort) < = 1:

return toSort

# set the value to pivot around
pivot = toSort[0] # initialize lists
less = []
greater = []
# sort the list
# skip the first value
for item in toSort[1:]:

if item < = pivot:

less.append(item)

else:

greater.append(item)

# recurse on both lists
r = qsort(less)
r.append(pivot)
r.extend(qsort(greater))
return r

# test
x = [1,99,7,0,7,7,7,99999,8,9,14,74,88]
print qsort(x)

This example is not very useful since python lists have a built in sort function, but should you have a list of tuples that you wanted to sort this function could very easily be modified to work with a value within the tuple that it pulls out instead of sorting by just the item itself.

This entry was posted on Thursday, January 18th, 2007 at 5:39 pm and is filed under Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Python Quicksort”

  1. Bob Farrell Says:
    May 14th, 2008 at 8:31 am

    I think it’s a good idea to note that the Python list sort can take a “key” argument, so you would do, e.g.:
    yourlist.sort( key=operator.itemgetter(x) )
    Where yourlist is a list of tuples and x is the index you wish to sort by.

    Usually a good idea to read the docs before publishing. :-)

Leave a Reply