« 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.

2 Responses to “Python Quicksort”

  1. Steve (Frostbyte) says:
    October 23, 2008 at 9:24 am

    def qsort(items):
    count = len(items)
    if count <= 1:
    return items
    pivot = items[0]
    return qsort(filter(lambda x: x pivot, items))

  2. Steve (Frostbyte) says:
    October 23, 2008 at 9:24 am

    def qsort(items):
    count = len(items)
    if count <= 1:
    return items
    pivot = items[0]
    return qsort(filter(lambda x: x < pivot, items)) + [pivot] + sort(filter(lambda x: x > pivot, items))

Leave a Reply