import time
import numpy as np
import matplotlib.pyplot as plt

def selection_sort(arr):
    for i in range(len(arr)):
        k = i

        for j in range(i+1, len(arr)):
            if arr[j] < arr[k]:
                k = j

        if k != i:
            arr[i], arr[k] = arr[k], arr[i]


def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j+1] = key


def bubble_sort(arr):
    n = len(arr) - 1

    while n >= 1:
        i = 0

        while i < n:

            if arr[i] > arr[i + 1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
            
            i = i+1
            
        n = n - 1

sorts = [
    {
        "name":"Insertion Sort",
        "sort":lambda arr: insertion_sort(arr)
    },
    {
        "name":"Selection Sort",
        "sort":lambda arr: selection_sort(arr)
    },
    {
        "name":"Bubble Sort",
        "sort":lambda arr: bubble_sort(arr)
    }
]

elements = np.array([i * 1000 for i in range(1,10)])

plt.xlabel("List Length")
plt.ylabel("Time Complexity")

for sort in sorts:
    times = list()
    start_all = time.time()
    for i in range(1, 10):
        start = time.time()
        a = np.random.randint(1000, size = i * 1000)
        sort["sort"](a)
        end = time.time()
        times.append(end - start)

        print(sort["name"], "Sorted", i * 1000, "Elements in", end - start, "s")
    end_all = time.time()
    print(sort["name"], "Sorted Elements in", end_all - start_all, "s")

    plt.plot(elements, times, label = sort["name"])

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