#
# Implementation of quicksort as a demonstration of recursion
#
import random
howmany = 25 # how many elements in the ist to be sorted
#
# find the dividing point (index), called the pivot, that partitions L into two parts
# such that everything with an index less than
def partition(L, lo, hi):
# the first value will be the pivot
pivot = L[lo]
# we start at the beginning, so need to back each up 1
lo -= 1
hi += 1
while True:
# advance the lower index
# and go until you find something
# at least as big as the pivot
lo += 1
while L[lo] < pivot:
lo += 1
# advance the upper index
# and go until you find something
# as small as as the pivot
hi -= 1
while L[hi] > pivot:
hi -= 1
# if lo and hi cross, return hi as the pivot
if lo >= hi:
return hi
# otherwise, swap the lo and hi and continue
L[lo], L[hi] = L[hi], L[lo]
#
# the quicksort: split the list in two,
# then sort each part separately
# the partition ensures all elements in the first part
# is less than every element in the second part
# note we are only sorting lnum[lo] .. lnum[hi] inclusive
#
def quicksort(lnum, lo, hi):
#b ase case: 0 or 1 elements in list, so nothing to sort
if len(lnum) < 2:
return
# see if the bounds of the list make sense
if lo < hi:
# they do -- find the dividing point
p = partition(lnum, lo, hi)
# recurse: sort the two partitions independently
quicksort(lnum, lo, p)
quicksort(lnum, p+1, hi)
#
# populate the list with some random numbers
# and print it out
#
numbers = []
for i in range(howmany):
numbers.append(int(random.random()*100))
for i in numbers:
print "%2d" % (i),
print
#
# sort it
#
quicksort(numbers, 0, howmany - 1)
#
# print the sorted list
#
for i in numbers:
print "%2d" % (i),
print