class node:
  def __init__ ( self, data = None, link = None ):
    self.data = data
    self.link = link

# timing Micko's 6 sorting algorithms 11/27/2005
 
import random  # for generating random numbers
import time    # for timing each sort function with time.clock()
 
N = 1000     # number of elements
lista = []   # list of comparable elements
 
for i in range ( 0, N ) :
  lista.append ( int ( random.uniform ( 0, N ) ) )
 
def print_timing(func):
  def wrapper(*arg):
    t1 = time.clock()
    res = func(*arg)
    t2 = time.clock()
    print '%s took %0.3fms.' % (func.func_name, (t2-t1)*1000.)
    return res
  return wrapper
 
# declare the @ decorator just above each sort function, invokes print_timing()
@print_timing
def bubble_sort( lista ):
  swap_test = False
  for i in range ( 0, len ( lista ) - 1 ):
    for j in range ( 0, len ( lista ) - i - 1 ):
      if lista[j] > lista[j + 1] :
        lista[j], lista[j + 1] = lista[j + 1], lista[j] # swap
        swap_test = True
    if swap_test == False:
      break
 
# selection sort
@print_timing
def selection_sort( lista ):
  for i in range ( 0, len ( lista ) ):
    min = i
    for j in range ( i + 1, len ( lista ) ):
      if lista[j] < lista[min] :
        min = j
    lista[i], lista[min] = lista[min], lista[i]
 
# insertion sort
@print_timing
def insertion_sort( lista ):
  for i in range ( 1, len ( lista ) ):
    save = lista[i]
    j = i
    while ( j > 0 and lista [j - 1] > save ):
      lista[j] = lista[j - 1];
      j -= 1
    lista[j] = save
 
# quick sort
@print_timing
def quick_sort( lista ):
  quick_sort_r( lista, 0, len ( lista ) - 1 )
# end quick_sort
 
# quick_sort_r, recursive (used by quick_sort)
def quick_sort_r( lista , first, last ):
  if last > first :
    pivot = partition ( lista, first, last )
    quick_sort_r ( lista, first, pivot - 1 )
    quick_sort_r ( lista, pivot + 1, last )
# end quick_sort_r
 
# partition (used by quick_sort_r)
def partition( lista, first, last ):
  sred = ( first + last ) / 2
  if lista[first] > lista [sred] :
    lista[first], lista [sred] = lista [sred], lista[first]
  if lista[first] > lista [last] :
    lista[first], lista[last] = lista[last], lista[first]
  if lista[sred] > lista[last] :
    lista[sred], lista[last] = lista[last], lista[sred]
  lista [sred], lista [first] = lista[first], lista[sred]
 
  pivot = first
  i = first + 1
  j = last
 
  while ( True ):
    while ( i <= last and lista[i] <= lista [pivot] ):
      i += 1
    while ( j >= first and lista[j] > lista[pivot] ):
      j -= 1
    if i >= j :
      break
    else:
      lista[i], lista[j] = lista[j], lista[i]
  lista[j], lista[pivot] = lista[pivot], lista[j]
  return j
# end partition
 
# heap sort
@print_timing
def heap_sort( lista ):
  first = 0;
  last = len ( lista ) - 1;
  create_heap ( lista, first, last )
  for i in range ( last, first, -1 ):
    lista[i], lista[first] = lista[first], lista[i]
    establish_heap_property ( lista, first, i - 1 )
# end heap_sort
 
# create heap (used by heap_sort)
def create_heap( lista, first, last ):
  i = last / 2;
  while ( i >= first ):
    establish_heap_property ( lista, i, last )
    i -= 1
# end create_heap
 
# establish heap property (used by create_heap)
def establish_heap_property ( lista, first, last ):
  while 2 * first + 1 <= last :
    k = 2 * first + 1;
    if k < last and lista[k] < lista[k + 1] :
      k += 1
    if lista[first] >= lista[k] :
      break
    lista[first], lista[k] = lista[k], lista[first]
    first = k
# end establish_heap_property
 
# merge sort
@print_timing
def merge_sort( lista ):
  merge_sort_r ( lista, 0, len ( lista ) -1 )
# end merge_sort_r
 
# merge sort recursive (used by merge_sort)
def merge_sort_r( lista, first, last ):
  if first < last:
    sred = ( first + last ) / 2
    merge_sort_r ( lista, first, sred )
    merge_sort_r ( lista, sred + 1, last )
    merge ( lista, first, last, sred )
# end merge_sort_r
 
# merge (used by merge_sort_r)
def merge( lista, first, last, sred ):
  helper_list = []
  i = first
  j = sred + 1
  while ( i <= sred and j <= last ):
    if lista [i] <= lista [j] :
      helper_list.append ( lista[i] )
      i += 1
    else:
      helper_list.append ( lista [j] )
      j += 1
  while ( i <= sred ):
    helper_list.append ( lista[i] )
    i +=1
  while ( j <= last ):
    helper_list.append ( lista[j] )
    j += 1
 
  for k in range ( 0, last - first + 1):
    lista[first + k] = helper_list [k]
# end merge
 
 
# run test if script is executed
if __name__ == "__main__" :
  print "timing the 6 sorting algorithms with a list of 1000 integers:"
  bubble_sort( lista )
  heap_sort( lista )
  insertion_sort( lista )
  merge_sort( lista )
  quick_sort( lista )
  selection_sort( lista )
 
  raw_input( "Press Enter to continue..." )
 
"""
typical results:
bubble_sort took 426.132ms.
heap_sort took 28.322ms.
insertion_sort took 1.091ms.
merge_sort took 34.000ms.
quick_sort took 6.494ms.
selection_sort took 177.234ms.
"""