#!/usr/bin/python

import os
import sys
import time
import random
import cProfile
import itertools

profile_it = True

if profile_it:
	import quick_sort_py as quick_sort
else:
	import quick_sort as quick_sort

def append(filename, size, duration):
	file = open(filename, 'a')
	file.write('%d %f\n' % (size, duration))
	file.close()
	
def shuffle(lst):
	len_lst = len(lst)
	for index in xrange(len_lst):
#		percentage = index * 100.0 / len_lst
#		if index and percentage % 10 == 0:
#			print percentage
		random_index = int(random.random() * len_lst)
		lst[index], lst[random_index] = lst[random_index], lst[index]

def is_sorted(list_):
	if not list_:
		return True
	else:
		for left, right in itertools.izip(list_, list_[1:]):
			if left > right:
				return False
		return True

#for x in xrange(9):
#for x in xrange(7):
#for x in xrange(5):
#for x in xrange(3):

for x in [ 7 ]:
	size = 10**x
	#ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ]
	print 'starting getting %d (10**%d) consecutive integers, %s' % (size, x, time.ctime(time.time()))
	ints = range(size)
	print 'done getting %d consecutive integers, %s' % (size, time.ctime(time.time()))
	print 'starting shuffling %d consecutive integers, %s' % (size, time.ctime(time.time()))
	shuffle(ints)
	print 'done shuffling %d consecutive integers, %s' % (size, time.ctime(time.time()))

	ints_copy = ints[:]

	print 'starting int quick_sort', time.ctime(time.time())
	t0 = time.time()
	#result = quick_sort.insertion_sort(ints, 0, len(ints) - 1)
	if profile_it:
		cProfile.run('quick_sort.quick_sort(ints)')
	else:
		quick_sort.quick_sort(ints)
	t1 = time.time()
	print 'done with int sort', time.ctime(time.time())
	sys.stdout.flush()
	if is_sorted(ints):
		print 'sorted correctly'
	else:
		print 'sorted _in_correctly'
		print result
		sys.exit(1)
	sys.stdout.flush()
	diff_quick_sort = t1 - t0
	append('quick_sort.dat', size, diff_quick_sort)
	print 'quick sort time was', diff_quick_sort
	sys.stdout.flush()
	print 'starting tim sort', time.ctime(time.time())
	sys.stdout.flush()
	t0 = time.time()
	ints_copy.sort()
	t1 = time.time()
	print 'done with tim sort', time.ctime(time.time())
	sys.stdout.flush()
	diff_tim_sort = t1 - t0
	print 'tim sort time was', diff_tim_sort
	sys.stdout.flush()
	append('tim_sort.dat', size, diff_tim_sort)
	print 'quick sort time was %3.2f%% of the tim sort time' % (float(diff_quick_sort - diff_tim_sort) * 100.0 / diff_tim_sort)
	sys.stdout.flush()
	print