###################################################
# Importujemy biblioteki, które będziemy używać w programie
# random - generowanie randomowych liczb
# randint - generowanie randomowych integerów liczb
# time - do mozliwości obliczania aktualnie wykonywanego czasu skryptu
###################################################

import random
from random import randint
import time

###################################################
# Tworzymy funkcję do generowania liczb określająca ile liczb ma zostać wygenerowanych
# oraz jaka liczba ma być maksymalna z przedziału, pętla for generuje daną ilość liczb
# wyjściowych jako maksymalny zasięg wielkości listy wpisaną w funkcji
###################################################


def create_list(size=10, max=100000):
    return [randint(0, max) for _ in range(size)]


###################################################
# Generujemy zmienne z listą liczb nieposrotowanych do dalszego sortowania ich w skryptach
# create_list(wielkość_listy, maksymalna_wielkość_generowanej_liczby)
###################################################

lista100 = create_list(100, 100000)
lista1000 = create_list(1000, 100000)
lista10000 = create_list(10000, 100000)
lista100000 = create_list(100000, 100000)


###################################################
# Sortowanie bubbule sort, w tym przypadku jest to lepsza wersja ów skryptu, samo sortowanie
# bubble - czyli inaczej sortowanie bombelkowe polega na porównywaniu dwóch
# kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek,
# w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego
# przejścia nie dokonano żadnej zmiany.
###################################################

def bubblesort(list):
    # Pętla licząca wielkość listy, len() zwraca ilość obiektów w liście
    for iter_num in range(len(list)-1, 0, -1):
        # Tutaj rozpoczyna się sortowanie obiektów w liście czyli liczb
        for idx in range(iter_num):
            # Skrypt sprawdza dwa kolejne elementy w liście
            if list[idx] > list[idx+1]:
                # Jeżeli jest większa niż kolejny zamienia je kolejnością
                temp = list[idx]
                # Przypisuje wartość aktyalną z kolejną wartością z listy
                list[idx] = list[idx+1]
                list[idx+1] = temp
    # Zwracanie posortowanej listy obiektów
    return list

###################################################
# Sortowanie po przez wybór - jedna z prostszych metod sortowania o złożoności.
# Polega na wyszukaniu elementu mającego się znaleźć na żądanej pozycji i zamianie miejscami z tym,
# który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
###################################################


def selection_sort(list):

    for idx in range(len(list)):

        min_idx = idx
        for j in range(idx + 1, len(list)):
            if list[min_idx] > list[j]:
                min_idx = j

        list[idx], list[min_idx] = list[min_idx], list[idx]

    return list


def quicksort(list):
    if len(list) <= 1:
        return list
    pivot = list[len(list) // 2]
    left = [x for x in list if x < pivot]
    middle = [x for x in list if x == pivot]
    right = [x for x in list if x > pivot]

    return quicksort(left) + middle + quicksort(right)


def insertion_sort(list):

    for i in range(1, len(list)):
        j = i-1
        nxt_element = list[i]

        while (list[j] > nxt_element) and (j >= 0):
            list[j+1] = list[j]
            j = j-1
        list[j+1] = nxt_element

    return list


#######################
## SORTOWANIA BUBBLE ##
#######################

start_time = time.time()
print(bubblesort(lista1000))
print('\033[92m' + "[Bubble 100] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(bubblesort(lista1000))
print('\033[92m' + "[Bubble 1000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(bubblesort(lista1000))
print('\033[92m' + "[Bubble 10000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(bubblesort(lista1000))
print('\033[92m' + "[Bubble 100000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

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

##########################
## SORTOWANIA QUICKSORT ##
##########################

start_time = time.time()
print(quicksort(lista100))
print('\033[92m' + "[Quick 100] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(quicksort(lista1000))
print('\033[92m' + "[Quick 1000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(quicksort(lista10000))
print('\033[92m' + "[Quick 10000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(quicksort(lista100000))
print('\033[92m' + "[Quick 100000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

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

###################################################
## SORTOWANIA SELECTION SORT (PRZEZ WYBIERANIE) ##
###################################################

start_time = time.time()
print(selection_sort(lista100))
print('\033[92m' + "[Selection 100] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(selection_sort(lista1000))
print('\033[92m' + "[Selection 1000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(selection_sort(lista10000))
print('\033[92m' + "[Selection 10000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(selection_sort(lista100000))
print('\033[92m' + "[Selection 100000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

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

##################################################
## SORTOWANIA INSERTION SORT (PRZEZ WSTAWIANIE) ##
##################################################

start_time = time.time()
print(insertion_sort(lista100))
print('\033[92m' + "[Insertion 100] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(insertion_sort(lista1000))
print('\033[92m' + "[Insertion 1000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(insertion_sort(lista10000))
print('\033[92m' + "[Insertion 10000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

start_time = time.time()
print(insertion_sort(lista100000))
print('\033[92m' + "[Insertion 100000] Czas sortowania: %s sekund " %
      (time.time() - start_time) + '\033[0m')

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