#!/usr/bin/python3
import time
from random import randint, randrange

def bubbleSort(array):
	length = len(array)
	for i in range(0, length):
		is_sorted = True
		for j in range(0, length-i-1):
			if array[j] > array[j+1]:
				array[j], array[j+1] = array[j+1], array[j]
				is_sorted = False
		if is_sorted:
			break
	return array

def insertionSort(array):
	for i in range(1, len(array)):
		j = i
		while j > 0 and array[j-1] > array[i]:
			j -= 1
		if i != j:
			v = array[i]
			del array[i]
			array.insert(j, v)
	return array

def selectionSort(array):
	for i in range(len(array)):
		minimum = i
		for j in range(i, len(array)):
			if array[j] < array[minimum]:
				minimum = j
		if minimum != i:
			#array = array[:i] + [array[minimum]] + array[i:minimum] + array[minimum+1:]
			v = array[minimum]
			del array[minimum]
			array.insert(i, v)
	return array

def quickSort(array):
	if len(array) < 2:
		return array
	pivot = array[0]
	smaller, greater_equal = [], []

	for i in range(1, len(array)):
		if array[i] < pivot:
			smaller.append(array[i])
		else:
			greater_equal.append(array[i])
	return quickSort(smaller) + [pivot] + quickSort(greater_equal)

def quickMid(array):
	"""Pivot is in the middle of array."""
	l = len(array)
	if l < 2:
		return array

	pivot_idx = l // 2
	pivot = array[pivot_idx]
	smaller, greater_equal = [], []
	for i in range(0, l):
		if i != pivot_idx:
			a = array[i]
			if a < pivot:
				smaller.append(a)
			else:
				greater_equal.append(a)
	return quickMid(smaller) + [pivot] + quickMid(greater_equal)

def quickRand(array):
	"""Random position of a pivot."""
	l = len(array)
	if l < 2:
		return array

	pivot_idx = randrange(0, l)
	pivot = array[pivot_idx]
	smaller, greater_equal = [], []
	for i in range(0, l):
		if i != pivot_idx:
			a = array[i]
			if a < pivot:
				smaller.append(a)
			else:
				greater_equal.append(a)
	return quickRand(smaller) + [pivot] + quickRand(greater_equal)

def mergeSort(array):
	l = len(array)
	if l == 1:
		return array
	elif l == 2:
		return [min(array), max(array)]
	mid = l // 2
	a = mergeSort(array[:mid])
	b = mergeSort(array[mid:])

	p, i, j = 0, 0, 0
	# a should always be shorter than b (or of equal lengths).
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			array[p] = a[i]
			i += 1
		else:
			array[p] = b[j]
			j += 1
		p += 1

	if i == len(a):
		while j < len(b):
			array[p] = b[j]
			p += 1
			j += 1
	elif j == len(b):
		while i < len(a):
			array[p] = a[i]
			p += 1
			i += 1

	return array

def heapify(array, end, i):
	l = 2*i + 1
	r = 2*(i + 1)
	max = i
	if l < end and array[i] < array[l]:
		max = l
	if r < end and array[max] < array[r]:
		max = r
	if max != i:
		array[i], array[max] = array[max], array[i]
		if 2*max + 1 < end:
			heapify(array, end, max)

def heapSort(array):
	end = len(array)
	start = end // 2 - 1
	for i in range(start, -1, -1):
		heapify(array, end, i)
	for i in range(end-1, 0, -1):
		array[0], array[i] = array[i], array[0]
		heapify(array, i, 0)
	return array

# ------------------------------------------------------------

def test_procedure():
	# Naglowek tabeli.
	header = "{:>5} |" + 6*"{:>12}" + " |{:>12}"
	print(header.format("Size", "Bubble", "Insertion", "Selection", "Quick", "Merge", "Heap", "sorted()"))
	print("-" * 95)

	# Format pojedynczego wiersza tabeli:
	# N | czasy 6 algorytmow | czas sorted()
	row = "{:>5} |" + 6*"{:>12.6f}" + " |{:>12.6f}"

	for N in (1000, 5000, 10000, 12500, 15000, 20000, 25000, 30000, 35000, 40000):
		# Utworzenie N-elementowej tablicy danych.
		data = [randint(0, 4096) for _ in range(0, N)]
		start_t = time.time()

		bub = bubbleSort(data[:])
		bub_t = time.time()

		ins = insertionSort(data[:])
		ins_t = time.time()

		sel = selectionSort(data[:])
		sel_t = time.time()

		qui = quickSort(data[:])
		qui_t = time.time()

		mer = mergeSort(data[:])
		mer_t = time.time()

		hea = heapSort(data[:])
		hea_t = time.time()

		# Do celow porownawczych.
		sor = sorted(data[:])
		sor_t = time.time()

		print(row.format(N, bub_t-start_t, ins_t-bub_t, sel_t-ins_t, qui_t-sel_t, mer_t-qui_t, hea_t-mer_t, sor_t-hea_t))

def quickVariation():
	header = "{:>5} |" + 3*"{:>12}"
	print(header.format("Size", "Quick", "QuickMid", "QuickRand"))
	print("-" * 95)

	row = "{:>5} |" + 3*"{:>12.6f}"

	for N in (50, 100, 250, 500, 1000, 5000, 10000, 12500, 15000, 20000, 25000, 30000, 35000, 40000):
		data = [N - i for i in range(0, N)]

		if N < 1000:
			try:
				start_t = time.time()
				qs = quickSort(data[:])
				qs_d = time.time() - start_t
			except Exception:
				qs_d = float('NaN')
		else:
			qs_d = float('NaN')

		start_t = time.time()

		qm = quickMid(data[:])
		qm_t = time.time()

		qr = quickRand(data[:])
		qr_t = time.time()

		print(row.format(N, qs_d, qm_t-start_t, qr_t-qm_t))

if __name__ == "__main__":
	#test_procedure()
	quickVariation()