import random

# générer une liste "aléatoire"
l = []
for x in range(101):
    l.append(random.randint(1,501))

def bubblesort(liste):
    swap = True # retient s'il y a eu échange
    nb_op = 0   # estimer la complexité
    while swap:
        swap = False
        for i in range(0,len(liste)-1):
            nb_op += 1
            if liste[i]>liste[i+1]:
                liste[i], liste[i+1] = liste[i+1], liste[i]
                swap = True
    print(nb_op)
    return(liste)

def bubblesort2(liste):
    swap = True # retient s'il y a eu échange
    fin = len(liste)-1 # jusqu'où parcourt-on la liste
    while swap:
        swap = False
        for i in range(0,fin):
            if liste[i]>liste[i+1]:
                liste[i], liste[i+1] = liste[i+1], liste[i]
                swap = True
        fin -= 1
    return(liste)

def insertionsort(liste):
    # remarque : on commence avec i=1 (et pas 0)
    for i in range(1, len(liste)): 
            element = liste[i] # on mémorise l'élément
            # déplacer, un à un, les éléments de liste[0:i-1]
            # qui sont plus grands que "element"
            j = i-1
            while j >= 0 and element < liste[j]: 
                liste[j + 1] = liste[j] 
                j -= 1
            liste[j + 1] = element
    return(liste) 


# on suppose que le pivot est l'élément liste[sup]
# modifie la liste dans l'intervalle liste[inf],...,liste[sup]
def partition(liste, inf, sup): 
    i = inf-1  # indice du dernier élt. plus petit que le pivot         
    pivot = liste[sup]      
    for j in range(inf, sup): 
        if liste[j] <= pivot:  
           i = i+1 
           liste[i],liste[j] = liste[j],liste[i] 
    liste[i+1], liste[sup] = liste[sup], liste[i+1] 
    return (i+1) # renvoie la position du pivot 

def quicksort(liste,inf,sup): 
    if inf<sup: 
        pi = partition(liste,inf,sup) # liste[pi] est bien positionné
        # on recommence récursivement
        quicksort(liste, inf, pi-1) 
        quicksort(liste, pi+1, sup) 

def mergesort(liste): 
    if len(liste) >1: 
        milieu = len(liste)//2  
        G = liste[:milieu]   # on travaille sur des copies
        D = liste[milieu:]   # on a coupé liste en 2
        mergesort(G) 
        mergesort(D)

        # procéder à la fusion au sein de liste
        i = j = k = 0  
        while i < len(G) and j < len(D): 
            if G[i] < D[j]: 
                liste[k] = G[i] 
                i+=1
            else: 
                liste[k] = D[j] 
                j+=1
            k+=1
          
        # Quand on sort de la boucle, on n'a pas
        # nécessairement parcouru tout G ou L,  
        while i < len(G): 
            liste[k] = G[i] 
            i+=1
            k+=1  
        while j < len(D): 
            liste[k] = D[j] 
            j+=1
            k+=1

