## Tri à bulle : exemple de tri non inclus dans le cours
# On parcourt le tableau de gauche à droite et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l'ordre, ils sont échangés.
# Après un premier parcours complet du tableau, le plus grand élément est forcément en fin de tableau, à sa position définitive. Il n'a plus à être traité.
# Le reste du tableau est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s'arrêtant à l'avant-dernier élément.
# Après ce deuxième parcours, les deux plus grands éléments sont à leur position définitive. Il faut donc répéter les parcours du tableau, jusqu'à ce que les deux plus petits éléments soient placés à leur position définitive, en début de liste

import time
import numpy as np


def tri_methode(L):
    ''' utilise la méthode de tri préintégrée dans Python, optimale'''
    t1=time.perf_counter() # on lance le chronomètre
    copy=list(L)
    copy.sort()
    t2=time.perf_counter() # on arrête le chronomètre
    return copy,(t2-t1)    # renvoie la liste triée, et le temps mis (en s)


def tri_bulle(L):
    t1=time.perf_counter() # on lance le chronomètre
    copy=list(L)
    # On pointe (i) les éléments les uns après les autres, de droite à gauche
    for i in range(len(copy)-1,0,-1): # i : position d'arrêt des échanges
        # On parcourt les éléments précédents : de 0 à i-1 inclus
        for j in range(i):
            # On échange les éléments si celui de gauche est > à celui de droite
            # Ainsi on envoie le plus grand à droite
            if copy[j]>copy[j+1]:
                copy[j],copy[j+1]=copy[j+1],copy[j]
    t2=time.perf_counter() # on arrête le chronomètre
    return copy,(t2-t1)    # renvoie la liste triée, et le temps mis (en s)


# liste de longueur 5000 avec des entiers aléatoires entre 0 inclus et 50 exclu
L = np.random.randint(0,50,5000)


L_tri_Python = tri_methode(L) ; print(L_tri_Python[1]) # on affiche le temps mis (s)

L_tri_bulle = tri_bulle(L) ; print(L_tri_bulle[1]) # on affiche le temps mis (s)

## Vous remarquerez l'inefficacité temporelle du tri à bulle