#
# 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