#Main function that is called as soon as the program executes.
def main():
	print  '''Help Menu :
			1. Bubble Sort,
			2. Selection Sort,
			3. Merge Sort,
			4. Quick Sort,
			5. Insertion Sort'''
	num=raw_input("Which sorting algo would you like to run?");
	options = {'1' : bubblesort,
           '2' : selectionsort,
           '3' : mergesort,
           '4' : quicksort,
           '5' : insertionsort,
	} #Declaring a dictionary
	options.get(num, errorMessage)()


if __name__ == '__main__':
	main() #Called as soon as the program runs.

#Function used to build array from user input.
def createarr():
	arr = [] #Declaring an array
	elem = int(raw_input("How many elements you want?\t "))  #creating a size limit for array.
	for i in range(0, elem):
    		arr.append(int(raw_input("Enter number "+str(i+1)+":" ))) #Accepting array elements & appending to the array. This is not complicated. Look carefully. We are just concatenating & i+1 is because the array starts from 0. To make it more user friendly, we must start from 1.
	return arr #Printing the array values.

#Acts as default function for invalid user input.
def errorMessage():
    print "Incorrect input. Please enter a number between 1 and 5."

	

def bubblesort():
	print "You selected bubble sort. \n"
	newarr=createarr() #Calling function createarr() to build an array & pass the value to a local array.
	print "Before sorting the array is ", newarr
	done = 0 #Here done is the boolean variable
	while (done!=1): #while for checking if finished or not
		done=1 #set boolean to 1 if finished
		for i in range(1,len(newarr)):  #loop through the array
			if(newarr[i-1]>newarr[i]): #check if previous is greater than the next item in array
				done = 0 #set done to 0 to keep going on.
				tmp = newarr[i-1] #Perform swap between them
				newarr[i-1]=newarr[i]
				newarr[i]=tmp
	print "After sorting the array is ", newarr #once done = 1, generate the final array.
####################################################################################

	

def selectionsort():
	print "You selected selection sort. \n"
	newarr=createarr()
	print "Before sorting the array is", newarr
	for i in range(0,len(newarr)-1): #looping through array
		m=i #setting position for min value
		for j in range(i+1,len(newarr)): #to move through loop leaving the min value
			if(newarr[j]<newarr[m]): #checking if next element is less than min value, #if it is min then
				m=j #switching position
		temp = newarr[i] #Now swapping
		newarr[i]=newarr[m]
		newarr[m]=temp
	print "After sorting the array is", newarr
####################################################################################

	

def mergesort():
	print "You selected merge sort. \n"
	newarr=createarr()
	print "Before sorting the array is", newarr
	print "After sorting the array is", divide(newarr) #Calling divide() function and passing the array as argument

def divide(arrToDivide):
	if (len(arrToDivide))<=1:
		return arrToDivide #check if there is just a single element in the array.

	middle = len(arrToDivide)/2 #Divide given array in two parts left and right
	left = arrToDivide[:middle] #Left partition of array. You should read more on lists in python and how do we access list elements
	right = arrToDivide[middle:] #Right partition of array

	left = divide(left) #Recursive call for further partitioning.
	right = divide(right)
	return merge(left,right) #Calling merge() function which generates the output for divide() function which is returned to margesort() as final sorted array

def merge(left,right):
	result = [] #Creating new array named result
	leftID=0 #Initializing left index variable
	rightID=0 #Initializing right index variable
	while leftID<len(left) and rightID<len(right): #change sequence to change sorting sequence
		if left[leftID]<=right[rightID]: #ex, if first of left <= first of right
			result.append(left[leftID]) #then append left to result
			leftID+=1
		else:
			result.append(right[rightID]) #else append right to result
			rightID+=1
	if left:		#merge sorted halfs back to single array result
		result.extend(left[leftID:])
	if right:
		result.extend(right[rightID:])
	return result
####################################################################################

	

def quicksort():  
	print "You selected quick sort. \n"
	newarr=createarr()
	print "Before sorting the array is", newarr
	print "After sorting the array is", sort(newarr) #Output of sort() function

def sort(newarr): #This is where quick sort actually occurs
	less = [] #List of elements less than pivot value
	greater = [] #List of elements greater than pivot value
	pivotequal = [] #List of elements equal to pivot value
	if len(newarr)<=1:
		return newarr #if there is single element in list
	else:
		pivot = newarr[0] #Initializing pivot to first element (default)
		for i in newarr:
			if i<pivot:	#If element is less than pivot
				less.append(i) #then append to less list
			elif i>pivot: #If element is greater than pivot
				greater.append(i) #then append to greater list
			else:	#if equal to pivot
				pivotequal.append(i)#then append to pivotequal list
		less = sort(less) #Recursive call to sort both new partitions
		greater = sort(greater)
		return less+pivotequal+greater #Join left, middle & right to output

####################################################################################

	

def insertionsort():  
	print "You selected insertion sort. \n"
	newarr=createarr()
	print "Before sorting the array is", newarr
	print "After sorting the array is", insertion(newarr)

def insertion(iarr):
	for i in range(1,len(iarr)): #Looping through elements in list
		value = iarr[i] #initializing key element
		j=i-1 #index of element previous to key element
		while (j>=0) and (iarr[j]>value): #checking if j is greater than 0 and value of element previous to key element is greater
			iarr[j+1] = iarr[j] #Shifting ahead
			j=j-1 #Moving back
		iarr[j+1] = value #Changing value of key element to next element
	return iarr
####################################################################################