#Programmer: Sriram Pemmaraju
#Date: March 26th, 2009
import random

# generate a random list of integers
# list size = n, range of ints: 1 to max
def genIntList(n, max):
    # we are generating a new list so define it
    lst = []
    for i in range(n):
        # create a new random integer (r)
        r = random.randint(1, max)

        # append this random integer to our list
        lst.append(r)

    # return our list
    return lst


# This swaps the contents of slots i and j in list C
def swap(C, i, j):
  temp = C[i]
  C[i] = C[j]
  C[j] = temp

# This is the implementation of the bubble sort algorithm
# discussed in class on March 13th and23rd
def bubbleSort(C):
  n = len(C)
  
  # i is an index that is required to travel from 0 to n-2,
  # thus pointing from the first array slot to the last-but-one slot
  for i in range(0, n-1):
    # j is an index that travels from the last-but-one slot in the
    # array to slot i. 
    # Example: n = 10, i = 4. The slots are indexed 0,1,..,9 and we
    # want j to travel from 8 down to 4.
    for j in range(n-2, i-1, -1):
      if(C[j] > C[j+1]):
        swap(C, j, j+1)

# Using the element C[left] as pivot, this method partitions
# the subarray C[left..right] into three "blocks": C[left..p-1], 
# C[p] and C[p+1..right] such that everything in the first block
# is less than C[p] and everything in the third block is greater
# than or equal to C[p]. The index p is returned.
# This method is key to the success of QuickSort
def partition(C, left, right):
  # If you want to implement randomized quick sort just uncomment the 
  # next two lines of code
  # p = random.randint(left, right)
  # swap(list, left, p)
		
  p = left
  
  # Scan elements in slots p+1 through last and compare with C[p]
  # and reposition if necessary
  for i in range(p+1, right+1):
    if(C[i] < C[p]):
      swap(C, i, p+1)
      swap(C, p, p+1)
      p = p + 1

  return p


def recursiveQuickSort(C, left, right):
  if(left < right):
    p = partition(C, left, right)
    recursiveQuickSort(C, left, p-1)
    recursiveQuickSort(C, p+1, right)

# The wrapper function around recursiveQuickSort so that the 
# user does not have to type extra arguments, whose sole purpose
# is to control the recursion.
def quickSort(C):
  left = 0
  right = len(C)-1
  recursiveQuickSort(C, left, right)