###################################################
# 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):
    # Skrypt sprawdza wielkość obecnie wprowadzonej listy
    for idx in range(len(list)):
        # Skrypt wyznacza minimalną wartość
        min_idx = idx
        # Pętla sprawdza indeks danych wartości w liście
        for j in range(idx + 1, len(list)):
            # Jezeli wczesniejsza wartość jest większa od kolejnej w liście
            if list[min_idx] > list[j]:
                # Zamienia je miejscami i przypisuje indeks wartości poprzedzającej
                min_idx = j
        # Skrypt przypisuje danym wartością z listy indeksy wartości posrotowanej tablicy dla wszystkich liczb
        list[idx], list[min_idx] = list[min_idx], list[idx]
    # Skrypt zwraca posortowaną listę
    return list

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

###################################################
# Sortowanie Quicksort, czyli tzw szybkie sortowanie. Z tablicy wybiera się element rozdzielający,
# po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie
# większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową
# i końcową część tablicy. Rekurencja kończy się, gdy kolejny fragment uzyskany z
# podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.
###################################################


def quicksort(list):
    # Jeżeli ilosć elementów w liście jest mniejsza lub równa 1 zwraca listę, wtedy nie potrzeba sortowania
    if len(list) <= 1:
        return list
    # Element rozdzielający tablice
    pivot = list[len(list) // 2]
    # Wyznaczanie wartości po lewej stronie
    left = [x for x in list if x < pivot]
    # Wyznaczanie wartości po środku
    middle = [x for x in list if x == pivot]
    # Wyznaczanie wartości po prawej stronie
    right = [x for x in list if x > pivot]

    # Zwraca posrotowaną listę
    return quicksort(left) + middle + quicksort(right)

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

###################################################
# Sortowanie przez wstawianie - Ten rodzaj sortowania możemy porównać do układania kart pokerzysty.
# Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także
# wstawiamy między odpowiednie karty i tak układamy zestaw kart
###################################################


def insertion_sort(list):
    # Skrypt oblicza wielkość listy
    for i in range(1, len(list)):
        # Skrypt bierze sobie poprzednią wartość ze zbioru
        j = i-1
        # Sprawdzamy miejsce następnego elementu
        nxt_element = list[i]
        # Pętla wykonuje się ciąle do momentu kiedy liczby są zamieniane z następnymi
        while (list[j] > nxt_element) and (j >= 0):
            # Wstawiamy liczbę między poprzedzającą i kolejną
            list[j+1] = list[j]
            # Indeks wcześniejszej liczby
            j = j-1
        # Indeks liczby kolejnej
        list[j+1] = nxt_element
    # Zwracanie listy posrotowanej
    return list

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

#######################
## SORTOWANIA BUBBLE ##
# start_time = time.time() - pobieramy aktyalny czas aby móc zmierzyć czas trwania skryptu
# print(bubblesort(lista1000)) - wyświetlanie i wykonywanie skryptu sortowania na liscie 1000 randomowych liczb
# print('\033[92m' + "[Bubble 100] Czas sortowania: %s sekund " % - \033[92m przypisuje kolor zielony do wyświetlanej informacji
#      (time.time() - start_time) + '\033[0m') - odejmujemy aktualny czas od czasu startowego, w tym przypadku obliczamy ilość
#                                                sekund potrzebnych do wykonana skryptu tzw. execution time script
#######################


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')

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