Algorithm-3 Time complexity by Algorithms

import time 
from numpy.random import seed 
from numpy.random import randint 
import matplotlib.pyplot as plt 
import numpy as np

import sys

#/////////////////재귀한도 깊이 설정
def func(n):
    if n == 1500:
        return
    func(n + 1)

if __name__=='__main__':
    sys.setrecursionlimit(2000)
    func(1)
#/////////////////재귀한도 깊이 설정



def Insertion_Sort(array):
    for a in range(1, len(array)):
        for b in range(a, 0, -1):
            if array[b] < array[b-1]:
                   array[b], array[b-1] = array[b-1], array[b]
            else:
                   break
    return array



def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result


def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list    

    mid = len(unsorted_list)//2
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]

    left1 = merge_sort(left)
    right1 = merge_sort(right)

    return merge(left1, right1)

def heapify(unsorted, index, heap_size):        #max heap 만들기
    largest = index
    
    left_index = 2*index + 1
    right_index = 2*index + 2

    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index

    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index

    if largest != index : 
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
    n = len(unsorted)

    for i in range(n//2 -1, -1, -1):
        heapify(unsorted, i, n)

    for i in range(n-1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)

    return unsorted


def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if( ARRAY_LENGTH <= 1):
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
        LESSER = [ element for element in ARRAY[1:] if element <= PIVOT ]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)


#Test Code
elements_insertion = list() 
elements_merge = list() 
elements_heap = list() 
elements_quick = list() 

times_insertion = list() 
times_merge = list() 
times_heap = list() 
times_quick = list() 

iteration = 20

for i in range(1, iteration): 
    #a = randint(0, 1000 * i, 1000 * i)
    a = np.array(range(100 * i, 0, -1))

    start = time.clock() 
    #Insertion_Sort(a) 
    end = time.clock() 
    print(len(a), "Elements Sorted by InsertionSort in ", end-start) 

    elements_insertion.append(len(a)) 
    times_insertion.append(end-start) 


for i in range(1, iteration): 
    #a = randint(0, 1000 * i, 1000 * i) 
    a = np.array(range(100 * i, 0, -1))

    start = time.clock() 
    merge_sort(a) 
    end = time.clock() 

    elements_merge.append(len(a)) 
    times_merge.append(end-start) 
print(len(a), "Elements Sorted by mergeSort in ", end-start) 


for i in range(1, iteration): 
    #b = randint(0, 1000 * i, 1000 * i) 
    b = np.array(range(100 * i, 0, -1))
    start = time.clock() 
    heap_sort(b) 
    end = time.clock() 

    elements_heap.append(len(b)) 
    times_heap.append(end-start) 
print(len(b), "Elements Sorted by HeapSort in ", end-start) 


for i in range(1, iteration): 
    #b = randint(0, 1000 * i, 1000 * i) 
    b = np.array(range(100 * i, 0, -1))

    start = time.clock() 
    quick_sort(b) 
    end = time.clock() 

    elements_quick.append(len(b)) 
    times_quick.append(end-start) 
print(len(b), "Elements Sorted by QuickSort in ", end-start) 

  
plt.xlabel('List Length') 
plt.ylabel('Time Complexity') 
plt.plot(elements_insertion, times_insertion, label ='Insertion Sort') 
plt.plot(elements_merge, times_merge, label ='Merge Sort') 
plt.plot(elements_heap, times_heap, label ='Heap Sort') 
plt.plot(elements_quick, times_quick, label ='Quick Sort') 


plt.grid() 
plt.legend() 
plt.show()