Random: After reading a few pages from "Introduction to Algorithms," (by Cormen et al.) I wrote this little code snippet to remind myself how to do a recursive quicksort! I think it is something like this... (O{n lg n} best case, right?)
#!/usr/bin/env python
# encoding: utf-8
"""
quickSort.py
"""
def quickSort(unsortedList):
# if the length of the unsorted list is less than one
# return it
if len(unsortedList) <= 1:
return unsortedList
# Otherwise, do this...
# Choosing roughly the middle element as the pivot
pivotIndex = int(len(unsortedList)/2)
print "Pivot Index " + str(pivotIndex)
pivotElement = unsortedList.pop(pivotIndex)
print "Pivot Element " + str(pivotElement)
# Lists to hold greater than and less than elements
lessThanList = []
greaterThanList = []
# For each item, place into a
for item in unsortedList:
if item <= pivotElement:
lessThanList.append(item)
else:
greaterThanList.append(item)
print "Less Than Array is: "
print lessThanList
print "Greater Then Array is: "
print greaterThanList
print
# Create a new list to concat sublists
sortedList = []
if len(lessThanList) > 0:
sortedList.extend(quickSort(lessThanList))
sortedList.append(pivotElement)
if len(greaterThanList) > 0:
sortedList.extend(quickSort(greaterThanList))
return sortedList
def main():
myList = [99,87,234,4,5,222,5,7]
mySortedList = quickSort(myList)
print "The final, sorted list is... "
print mySortedList
if __name__ == '__main__':
main()