Coursera Algo-005 Programming Question Set 2

quick_sort_comparisons.py

from math import floor
from sys import setrecursionlimit

setrecursionlimit(1000000)

"""
Use quick sort to explore pivoting rules.
TODO: Not working.
"""

with open('QuickSort.txt') as f:
  ints = [int(line) for line in f.readlines()]

print 'First 5 ints:{}'.format(ints[:5:])

comparisons = 0

def sort_array(array, left, right, pivot_chooser):
  global comparisons
  if len(array) == 1: return
  if left >= right: return
  i_pivot = pivot_chooser(array, left, right)
  #print 'pivot index', i_pivot
  i_pivot = partition_array(array, left, right, i_pivot)
  comparisons += right - left - 1
  #print 'partitioned', array
  sort_array(array, left, i_pivot - 1, pivot_chooser)
  sort_array(array, i_pivot + 1, right, pivot_chooser)
  return array

def partition_array(array, left, right, i_pivot):
  global comparisons
  pivot = array[i_pivot]
  #print 'pivot', pivot
  i = left + 1
  for j in range(i, right):
    j_n = array[j]
    #comparisons += 1
    if j_n < pivot:
      swap_in_array(array, i, j)
      i += 1
  #print 'unpivot'
  if i != left: swap_in_array(array, i - 1, left)
  return i

def swap_in_array(array, i, j):
  temp = array[i]
  array[i] = array[j]
  array[j] = temp
  #print 'swapped', array[i], array[j], array

def print_ints(): print ints if len(ints) < 100 else None

#ints = ints[:10:]
#ints = [3,9,8,4,6,10,2,5,7,1] # Should be 25, 29, 21.
print_ints()

"""
Number of comparisons if pivot is always first int.
"""
comparisons = 0
sort_array(ints[:], 0, len(ints) - 1, lambda array, left, right: left)
print_ints()
print 'question 1 comparisons', comparisons

"""
Number of comparisons if pivot is always last int.
"""
comparisons = 0
sort_array(ints[:], 0, len(ints) - 1, lambda array, left, right: right)
print_ints()
print 'question 2 comparisons', comparisons

"""
Number of comparisons if pivot is selected using median-of-three rule.
"""
def get_median_pivot(array, left, right):
  i_middle = int(floor((right - left) / 2))
  candidates = [array[left], array[i_middle], array[right]]
  candidates.sort()
  return array.index(candidates[1])

comparisons = 0
sort_array(ints[:], 0, len(ints) - 1, get_median_pivot)
print_ints()
print 'question 3 comparisons', comparisons