quicksort.py

def quicksort(array, start=None, end=None):
  """end is the index of the last element to be sorted"""
  if start is None and end is None:
    quicksort(array,0,len(array)-1)
    return array
  else:
    if start < end:
      pivot_index = partition(array,start,end)
      quicksort(array,start,pivot_index-1)
      quicksort(array,pivot_index+1,end)

def partition(array, start, end):
  pivot_index = end
  pivot = array[end]
  end -= 1
  going_right = True
  while start <= end:
    if going_right:
      if array[start] > pivot:
        going_right = False
      else:
        start += 1
    else:
      if array[end] < pivot:
        swap(array,start,end)
        start += 1
        going_right = True
      else:
        end -= 1
  if array[start] > pivot:
    swap(array,start,pivot_index)
    return start
  else:
    return pivot_index

def swap(array, a, b):
  temp = array[a]
  array[a] = array[b]
  array[b] = temp