#!/usr/bin/python

import sys
import time
import random
import funnelsort as funnelsort

def shuffle(lst):
	len_lst = len(lst)
	for index in xrange(len_lst):
		random_index = int(random.random() * len_lst)
		lst[index], lst[random_index] = lst[random_index], lst[index]

def gibberish(n):
	return [ ('spam ' * 10, 'eggs ' * 10, 'spam ' * 10, i) for i in xrange(n) ]

bad = False

for i in xrange(100):
#for i in [ 10 ]:
	print i,
	sys.stdout.flush()
	original_list = gibberish(i)
	#print original_list
	list_ = original_list[:]
	shuffle(list_)

	t0 = time.time()
	list_from_insertionsort = list_[:]
	funnelsort.insertionsort(list_from_insertionsort, 0, len(list_) - 1)
	t1 = time.time()
	insertion_diff = t1 - t0
	print insertion_diff,
	sys.stdout.flush()

	t0 = time.time()
	list_from_binarysort = list_[:]
	funnelsort.binarysort(list_from_binarysort, 0, len(list_) - 1)
	t1 = time.time()
	binary_diff = t1 - t0
	print binary_diff,
	print binary_diff / insertion_diff

	#print original_list
	#print list_from_insertionsort

	if list_from_insertionsort != original_list:
		print 'insertion sort problem', i
		bad = True

	if list_from_binarysort != original_list:
		print 'binary sort problem', i
		bad = True

if bad:
	print 'sort problems'
	sys.exit(1)