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.
def qsort(items):
count = len(items)
if count <= 1:
return items
pivot = items[0]
return qsort(filter(lambda x: x pivot, items))
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))
@Steve, your code won’t work on following array
>> qsort([2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,2,3])
>> [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] #skips duplicate values
Correction:
def qsort2(items):
if not items : return items
pivot = items[0]
return qsort2(filter(lambda x : x pivot,items[1:]))
>> qsort2([2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,2,3])
>> [2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]