import random as rd
import matplotlib.pyplot as plt
import time as t

## Q1 (générateur)
def generateur(n):
    return [rd.randint(1,n) for _ in range(n)]

## Q2 (minimum)
def minimum(liste):
    n = len(liste)
    i_min = 0
    for i in range(1,n):
        if liste[i] < liste[i_min]:
            i_min = i
    return i_min

## Q3 (tri par sélection - à trous)
def tri_selection(liste):
    n = len(liste)
    for i in range(n-1):
        i_min = i
        for j in range(i+1,n):
            if liste[j] < liste[i_min]:
                i_min = j
        liste[i], liste[i_min] = liste[i_min], liste[i]


## Q4 (temps - sélection)
for k in range(2,5):
    n = 10**k
    print("n=",n)
    liste = generateur(n)
    t0 = t.time()
    tri_selection(liste)
    t1 = t.time()
    print(t1 - t0)


## Q5 (tri par insertion - à trous)
def tri_insertion(seq):
    n = len(seq)
    for i in range(1,n):
        x = seq[i]
        j = i - 1
        while j >= 0 and seq[j] > x :
            j = j-1
        seq[j+2:i+1] = seq[j+1:i]
        seq[j+1] = x

## Q6 (temps - insertion)
for k in range(2,5):
    n = 10**k
    print("n=",n)
    liste = generateur(n)
    t0 = t.time()
    tri_insertion(liste)
    t1 = t.time()
    print(t1 - t0)


## Q7 - BONUS pour les plus rapides (insertion dichotomique)
def tri_insertion_dichotomique(seq):
    n = len(seq)
    for i in range(1,n):
        x = seq[i]
        g, d = 0, i
        while g < d:
            m = (g+d)//2
            if seq[m] <= x:
                g = m+1
            else:
                d = m
        seq[g+1:i+1] = seq[g:i]
        seq[g] = x

for k in range(2,6):
    n = 10**k
    print("n=",n)
    liste = generateur(n)
    t0 = t.time()
    tri_insertion_dichotomique(liste)
    t1 = t.time()
    print(t1 - t0)

## Q8 (tri bulle - à comprendre)
def tri_bulle(liste):
    n = len(liste)
    for i in range(n):
        for j in range(n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]


## Q9 (tri bulle amélioré - à trous)
def tri_bulle_ameliore(liste):
    n = len(liste)
    trie = False
    i = 0
    while not trie:
        trie = True
        for j in range(n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
                trie = False
        i = i + 1


## Q10 (temps - bulle / bulle amélioré)
for k in range(2,5):
    n = 10**k
    print("n=",n)
    liste = generateur(n)
    t0 = t.time()
    tri_bulle_ameliore(liste)
    t1 = t.time()
    print(t1 - t0)


## Q12 (comparaison graphique)
longueurs = list(range(100,1600,100))
liste_algos = [tri_selection,tri_insertion,tri_bulle]
temps = [[] for k in range(3)]
for n in longueurs:
    N = 10
    for k in range(3):
        tps = 0
        for i in range(N):
            liste = generateur(n)
            algo = liste_algos[k]
            t0 = t.time()
            algo(liste)
            t1 = t.time()
            tps += t1-t0
        temps[k].append(tps/N)
for k in range(3):
    algo = liste_algos[k]
    plt.plot(longueurs,temps[k],label=algo.__name__)
plt.legend(loc = "best")
plt.show()