import time
import random
def bubbleSort(list):
    for passnum in range(len(list)-1,0,-1):
        for i in range(passnum):
            if list[i]>list[i+1]:
                temp = list[i]
                list[i] = list[i+1]
                list[i+1] = temp
def quickSort(list):
   quickSortHelper(list,0,len(list)-1)

def quickSortHelper(list,first,last):
   if first<last:

       splitpoint = partition(list,first,last)

       quickSortHelper(list,first,splitpoint-1)
       quickSortHelper(list,splitpoint+1,last)


def partition(list,first,last):
   pivotvalue = list[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and list[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while list[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = list[leftmark]
           list[leftmark] = list[rightmark]
           list[rightmark] = temp

   temp = list[first]
   list[first] = list[rightmark]
   list[rightmark] = temp


   return rightmark

def mergeSort(list):
    print("Splitting ",list)
    if len(list)>1:
        mid = len(list)//2
        lefthalf = list[:mid]
        righthalf = list[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                list[k]=lefthalf[i]
                i=i+1
            else:
                list[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            list[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            list[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",list)
def insertionSort(list):
   for index in range(1,len(list)):

     currentvalue = list[index]
     position = index

     while position>0 and list[position-1]>currentvalue:
         list[position]=list[position-1]
         position = position-1

     list[position]=currentvalue
def selectionSort(list):
   for fillslot in range(len(list)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if list[location]>list[positionOfMax]:
               positionOfMax = location

       temp = list[fillslot]
       list[fillslot] = list[positionOfMax]
       list[positionOfMax] = temp
def makelist(list):
    print("1: Descending order to ascending order.")
    print("2: Random order to ascending order - the same random order will be used for each sorting algorithm.")
    while True:
        try:
            x = int(input())
        except:
            print("ERROR: please enter an integer.")
        if x == 1:
            print("Please enter the amount of values in the array.")
            while True:
                                try:
                                        n = int(input())
                                        break
                                except:
                                            print("ERROR: please enter an integer.")
            for i in range(0, n):
                list.append(n - 1)
            break
        elif x == 2:
            z = False
            while True:
                print("Please enter the amount of values in the array.")
                while True:
                                    try:
                                            n = int(input())
                                            break
                                    except:
                                            print("ERROR: please enter an integer.")
                print("Please enter the min value.")
                while True:
                                    try:
                                            min = int(input())
                                            break
                                    except:
                                            print("ERROR: please enter an integer.")
                print("Please enter the max value.")
                while True:
                                    try:
                                            max = int(input())
                                            break
                                    except:
                                            print("ERROR: please enter an integer.")
                if min < max:
                    break
                else:
                    print("ERROR: the min value needs to be smaller than the max value")
            for i in range(0, n):
                list.append(random.randint(min, max))
            break
        else:
            print("Please enter a valid number")
            x = input()
def sortlist(list):
    print("1: Bubble Sort")
    print("2: Quick Sort")
    print("3: Merge Sort")
    print("4: Insertion Sort")
    print("5: Selection Sort")
    print()
    print()
    print("0: Change list")
    while True:
        while True:
            try:
                y = int(input())
                break
            except:
                print("ERROR: please enter an integer.")
    if y == 0:
        start = time.time()
        makelist(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    elif y == 1:
        start = time.time()
        bubblesort(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    elif y == 2:
        start = time.time()
        quicksort(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    elif y == 3:
        start = time.time()
        mergesort(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    elif y == 4:
        start = time.time()
        insertionsort(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    elif y == 5:
        start = time.time()
        selectionsort(list)
        end = time.time()
        print("time taken: " + int(start - end) + "s"
    else:
        print("Please enter a valid number.")

def main():
    list = []
    makelist(list)
    sortlist(list)


main()