Some fundamental algorithms. Currently ; Insertion Sort, Merge Sort, Binary Search, Heap_Sort, Quick_sort

fundamental_algos.py

'''
Eren Golge - erengolge@gmail.com 
written for experience and experiment
'''

import pdb
import math
import random
import time
'''
TO DO:
-> set heap_sort able to sort in descending order
-> set heap_sort able to sort in place
-> tail_recursive_quick_sort does not work for some unknown REASON
'''

'''
INSERTION SORT
'''
def insertion_sort( A, inc_flag = True ):
    for j in range(2, len(A), 1):
        key = A[j]
        i = j - 1
        while ((inc_flag and A[i] > key) or (not inc_flag and A[i] < key)) and i >= 0:
            A[i+1] = A[i]
            i = i - 1
    	A[i+1] = key
    return A


# Find maximum sun subarray 
# does not work with all negative set
def max_subarray(A):
	left_so_far = 0
	right_so_far = 0

	left = 0
	right = 0

	max_so_far = 0
	up_to_here = 0

	for i,a in enumerate(A):
		up_to_here += a
		if up_to_here < 0:
			up_to_here = 0
			left = i +1
		else:
			up_to_here += a

		if up_to_here > max_so_far:
			max_so_far =up_to_here
			right_so_far = i 
			left_so_far = left 

	return max_so_far, left_so_far, right_so_far

'''
MERGER SORTY => theta(nlogn)
'''
def merge_sort(A, inc_flag = True):
	_merge_sort(A, 0, len(A)-1, inc_flag)

def _merge_sort(A,p,q, inc_flag):
	#pdb.set_trace()
	if p < q:
		r = (q+p)/2
		_merge_sort(A, p, r, inc_flag)
		_merge_sort(A, r+1, q, inc_flag)
		_merge_arrays(A, p, r, q, inc_flag)

def _merge_arrays(A, p, r, q, inc_flag):
	nL = (r-p+1)
	nR = (q-r)
	L = A[p:r+1]
	R = A[r+1:q+1]
	
	i = 0
	j = 0
	for k in range(p,q+1,1):
		if j < nR and i < nL:
			if (L[i] < R[j] and inc_flag) or (L[i] > R[j] and not inc_flag):
				A[k] = L[i]
				i += 1
			else:
				A[k] = R[j]
				j += 1
		elif i == nL and j < nR:
			A[k] = R[j]
			j += 1
		elif j == nR and i < nL:
			A[k] = L[i]
			i += 1
	return A


'''
BUBBLE SORT - O(n^2)
'''
def bubble_sort(A, inc_flag = True):
	for i in range(len(A)-1):
		for j in range(len(A)-1, 0, -1):
			cond = (A[j] < A[j-1] and inc_flag)  or (A[j] > A[j-1] and not inc_flag)
			if cond:
				temp = A[j]
				A[j] = A[j-1]
				A[j-1] = temp

'''
BINARY SEARCH - O(logn)
'''
def binary_search(A,x):
	if A[-1] < x or A[0] > x:
		return -1 

	left_last = 0
	right_last = len(A)-1
	result =  False
	while not result:
		#print left_last,' ', right_last
		indx = int(math.floor((left_last+right_last)/2))
		next_num = A[indx]
		if next_num == x:
			return indx
		elif next_num > x:
			right_last = indx
		else:
			left_last = indx
		if left_last + 1 == right_last:
			if A[left_last] == x:
				return left_last
			elif A[right_last] == x:
				return right_last
			else:
				return -1

'''
HEAP STRUCTURE and HEAP SORT
heapify > theta(log N)
build_max_heap > O(N)
heap_sort > theta(N logN) so Best Case = Worst Case 
'''
l_child_indx = lambda i : 2*i+1
r_child_indx = lambda i : 2*i+2

def swap(A,i,j):
	temp = A[i]
	A[i] = A[j]
	A[j] = temp

divide_floor = lambda A, k : int(math.floor(float(len(A)) / k))

# O(log n) correlated with the hegith of the heap tree
def heapify(A, i):
	left_child = l_child_indx(i)
	right_child = r_child_indx(i)
	largest = i
	if right_child < len(A) and A[right_child] > A[largest]:
		largest = right_child
	if left_child < len(A) and A[left_child] > A[largest]:
		largest = left_child
	if not largest  == i:
		swap(A, largest, i)
		heapify(A, largest)


# O(n) is the complexity with fine grained calculation
def build_max_heap(A):
	init_indx = divide_floor(A, 2)
	for i in range(init_indx, -1, -1):
		heapify(A,i)

# It only sorts in ascending order
def heap_sort(A):
	sorted_list = []
	build_max_heap(A)
	for i in range(len(A)-1, 0, -1):
		swap(A, i, 0)
		sorted_list.append(A.pop())
		heapify(A,0)
	sorted_list.append(A.pop())
	return sorted_list

'''
QUICK SORT 
O(N logN)>Best Case and Avg. Case 
O(N^2)> Worst Case
'''

def quick_sort(A, inc_flag = True):
	_quick_sort(A, 0, len(A)-1, inc_flag)

# In practise it's assumed to be more efficient partition method
def _hoare_partition(A, p, q, inc_flag):
	pivot = A[p]
	i = p
	j = q + 1
	while True:
		while True:
			i += 1
			if i > q or ((A[i] > pivot and inc_flag) or\
			 (A[i] < pivot and not inc_flag)) :
				break

		while True:
			j -= 1
			if j < p or ((A[j] < pivot and inc_flag) or\
			 (A[j] > pivot and not inc_flag)) :
				break

		if i < j:
			swap(A, i, j)
		elif j > p:
			swap(A,j,p)
			return j
		else:
			return p

def _partition(A, p, q, inc_flag):
	pivot = A[q]
	i = p-1
	for j in range(p, q, 1):
		cond  =  ( A[j] < pivot and inc_flag ) or ( A[j] > pivot and not inc_flag)
		if cond:
			i += 1
			swap(A,i,j)
	swap(A,q,i+1)
	return i+1

def _quick_sort(A, p, q, inc_flag):
	if p < q:
		r = _partition(A, p, q, inc_flag)
		#r = _hoare_partition(A, p, q, inc_flag)
		_quick_sort(A, p, r-1, inc_flag)
		_quick_sort(A, r+1, q, inc_flag)

# FOR SOME REASON IT DOES NOT WORK CORRECTLY
def tail_recursive_quick_sort(A, inc_flag = True):
#	_quick_sort(A, 0, len(A)-1, inc_flag)
	_tail_recursive_quick_sort(A, 0, len(A)-1, inc_flag)

def _tail_recursive_quick_sort(A, p, q, inc_flag):
	if p < q:
		r = _partition(A, p, q, inc_flag)
		_tail_recursive_quick_sort(A, p, r-1, inc_flag)
		p = r+1


'''
test functions
'''

if __name__ == '__main__':
	N = 2000
	inc_flag = True
	times = 10

	#a = [random.random() for _ in xrange(N)]	
	# start = time.time()
	# insertion_sort(a)
	# stop = time.time()
	# print 'Insertion Sort with size ',N, ' : ', stop - start
	
	#print max_subarray(a)

	# a = [random.random() for _ in xrange(N)]
	# start = time.time()
	# a_sorted = sorted(a, reverse = not inc_flag)
	# stop = time.time()
	# print 'Built-in Python sort with size ',N, ' : ', stop - start

	total_time = 0
	for i in range(times):
		a = [random.random() for _ in xrange(N)]
		a_sorted = sorted(a, reverse = not inc_flag)
		start = time.time()
		merge_sort(a, inc_flag)
		stop = time.time()
		total_time += stop - start
	print 'Merge Sort with size ',N, ' : ', total_time, 'sort order is ', a == a_sorted


	# a = [random.random() for _ in xrange(N)]
	# a_sorted = sorted(a, reverse = not inc_flag)
	# start = time.time()
	# bubble_sort(a, inc_flag)
	# stop = time.time()
	# print 'Bubble Sort with size',N, ' : ', stop - start, 'sort order is ', a == a_sorted

	# a = [random.random() for _ in xrange(N)]
	# a_sorted = sorted(a, reverse = True)
	# start = time.time()
	# sorted_a = heap_sort(a)
	# stop = time.time()
	# print 'Heap Sort with size',N, ' : ', stop - start, 'sort order is ', sorted_a == a_sorted

	total_time = 0
	for j in range(times):
		a = [random.random() for _ in xrange(N)]
		a_sorted = sorted(a, reverse = not inc_flag)
		start = time.time()
		quick_sort(a, inc_flag)
		stop = time.time()
		total_time += stop - start
	print 'Quick Sort with size',N, ' : ', total_time, 'sort order is ', a == a_sorted