import time
import random

def arrondi(x):
    return float('%.5g' % x)    # Arrondi x à 5 chiffres significatifs

def echanger(tab, i, j):
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def minimum_tableau(t, i_min):
    minimum = t[i_min]   # Le plus petit élément est pour l'instant le premier
    for i in range(i_min, len(t)):
        if t[i] < minimum:      # Si l'élément actuel est plus petit que le min
            i_min = i           # alors il devient le nouveau minimum et on note son indice
            minimum = t[i_min]  # et sa valeur
    return i_min

def tri_par_minimums_successifs(t):
    for i in range(len(t)-1):         # On parcours le tableau jusqu'à l'avant-derière case
        i_min = minimum_tableau(t, i) # On cherche le minimum
        if i_min != i:                # S'il n'est pas à la bonne place
            echanger(t, i, i_min)     # On échange pour le placer comme il faut

def tri_a_bulle(t):
    # On examine des tableaux de taille décroissante
    for iMax in range(len(t)-1, 0, -1): # la fin du tableau décroît jusqu'à 0
        for i in range(iMax):        # On parcours de 0 à iMax
            if t[i] > t[i+1]:        # Si les éléments ne sont pas dans le bon ordre
                echanger(t, i, i+1)  # on les permute

def partitionner(t, premier, dernier, pivot):
    echanger(t, pivot, dernier)
    j = premier
    for i in range(premier, dernier):
        if t[i] <= t[dernier]:
            echanger(t, i, j)
            j = j + 1
    echanger(t, dernier, j)
    return j

def tri_rapide_rec(t, premier, dernier):
    if premier < dernier:
        pivot = premier
        pivot = partitionner(t, premier, dernier, pivot)
        tri_rapide_rec(t, premier, pivot-1)
        tri_rapide_rec(t, pivot+1, dernier)

def tri_rapide(t):
    tri_rapide_rec(t, 0, len(t)-1)


def tri_fusion(t):
    if len(t) <= 1: # S'il ne reste qu'un élément ou moins
        return t    # alors c'est terminé
    else:
        t1 = t[0:len(t)//2].copy()     # Sinon on coupe le tableau
        t2 = t[len(t)//2:].copy()      # en deux sous-tableaux
        t = fusion(tri_fusion(t1), tri_fusion(t2)) # que l'on fusionne
        return t

def fusion(t1, t2):
    """Fusion de deux tableaux ordonnés"""
    if len(t2) == 0:                 # Si le deuxième tableau est vide
        return t1                    # on renvoit juste le premier
    t = [0]*(len(t1) + len(t2))      # Le tableau fusionné fait la taille de la somme de t1 et t2
    i1 = 0                           # indice sur le premier tableau (t1)
    i2 = 0                           # indice sur le deuxième tableau (t2)
    for i in range(len(t)):
        if t1[i1] <= t2[i2]:         # Si l'élément du 1er tableau est le plus petit
            t[i] = t1[i1]            # c'est lui qu'on place dans le tableau fusionné
            i1 = i1 + 1              # on incrémente l'indice du tableau 1, son élément étant placé
            if i1 >= len(t1):        # Si on a utilisé tout le tableau 1
                t[i+1:] = t2[i2:]    # on remplit le reste du tableau avec t2
                return t
        else:
            t[i] = t2[i2]            # Sinon on prend l'élément du tableau 2
            i2 = i2 + 1
            if i2 >= len(t2):        # Si on a utilisé tout le tableau t2
                t[i+1:] = t1[i1:]    # on remplit avec le reste du tableau t1
                return t
    return t                         # renvoit le tableau fusionné

def tri_a_peigne(t):
    intervalle = len(t)
    while intervalle > 1 or echange == True:
        intervalle = int(intervalle / 1.3)
        if intervalle < 1:
            intervalle = 1
        i = 0
        echange = False
        while i < (len(t) - intervalle):
            if t[i] > t[i+intervalle]:
                echanger(t, i, i+intervalle)
                echange = True
            i = i + 1

TAILLE_TABLEAU = 5000
NB_EXECUTIONS = 3
tests = [(tri_par_minimums_successifs, "par minimum successifs"),
         (tri_a_bulle, "à bulle"),
         (tri_rapide, "rapide (quicksort)"),
         (tri_fusion, "fusion"),
         (tri_a_peigne,"à peigne (combsort)")]

for tri in tests :
    duree = 0
    for n in range(NB_EXECUTIONS):
        t = [random.randint(0,10000) for n in range(TAILLE_TABLEAU)]
        debut = time.perf_counter()
        t = tri[0](t)
        fin = time.perf_counter()
        duree = duree + (fin - debut)
    duree = duree/NB_EXECUTIONS
    print("Temps d'exécution pour le tri", tri[1]," :",arrondi(fin-debut),"s")