###########################################
###########################################
## TP 08 : Méthodes de tri
###########################################
###########################################

## Importations

# pas d'importation

## Exercice 1 : effet de bord

def touchepas(L) :
    M = L[:] # M est une copie indépendante de L
    M[0] = -15
    return M

def touche(L) :
    L[0] = -15  # l'argument L est ici directement modifié
                # cette fonction n'a pas de 'return'

L = [1,2,3]
L2 = touchepas(L)
print(L,L2)

L = [1,2,3]
touche(L)
print(L)

## Exercice 2 : Tri naïf

def pos_min(L) :
    '''renvoie la position du minimum d'une liste de flottants non vide'''
    mini = L[0]
    imin = 0
    for i in range(len(L)) :
        if L[i] < mini :
            mini = L[i]
            imin = i
    return imin

L = [4,3,2,1,2,3,4,5]
assert pos_min(L) == 3

def tri_basique(L) :
    '''renvoie une liste triée sans effet de bord'''
    L2 = L[:]
    n = len(L2)
    M = []
    for _ in range(n) :
        i = pos_min(L2)
        x = L2.pop(i)
        M.append(x)
    return M

M = tri_basique(L)
print(L)
print(M)

## Exercice 3 : Tri par comptage

def multi(L,a) :
    '''compte les éléments a dans la liste L'''
    compteur = 0
    for elt in L :
        compteur += (elt == a)
    return compteur

L = [4,3,2,1,2,3,4,5]
assert multi(L,3) == 2
assert multi(L,6) == 0

def tri_bis(L) :
    '''tri par comptage d'une liste L d'entiers entre 0 et N'''
    N = max(L) # on pourrait coder cette recherche de maximum
    T = []
    for a in range(N+1) :
        T.append(multi(L,a))
    M = []
    for a in range(N+1) :
        M += T[a]*[a]
    return M

M = tri_bis(L)
assert M == [1,2,2,3,3,4,4,5]

## Exercice 4 : Tri-bulle

# le plus grand élément de la liste est toujours supérieur au suivant, donc il est permuté à chaque fois. Il se retrouve alors en fin de liste.

def permute(L,i,j) :
    '''permute dans la liste L les éléments d'indices i et j, avec effet de bord'''
    L[i],L[j] = L[j],L[i]

L = [4,3,2,1,2,3,4,5]
permute(L,0,7)
assert L == [5,3,2,1,2,3,4,4]

def bubblesort(L) :
    n = len(L)
    for i in range(n) :
        for j in range(n-1) : # on peut optimiser : range(n-1-i)
            if L[j] > L[j+1] :
                permute(L,j,j+1)

bubblesort(L)
assert L == [1,2,2,3,3,4,4,5]

## Exercice 5 : Tri-insertion

def retrograde(L,i) :
    while i > 0 and L[i-1] > L[i] :
        permute(L,i,i-1)
        i -= 1

def tri_insertion(L) :
    n = len(L)
    for i in range(len(L)) :
        retrograde(L,i)

L = [4,3,2,1,2,3,4,5]
tri_insertion(L)
assert L == [1,2,2,3,3,4,4,5]

## Exercice 6 : Tri-rapide

def quicksort(L) :
    n = len(L)
    if n <= 1 :
        return L
    else :
        pivot = L[0]
        Lgauche, Ldroite = [], []
        for i in range(1,n) :
            if L[i] < pivot :
                Lgauche.append(L[i])
            else :
                Ldroite.append(L[i])
        return quicksort(Lgauche) + [pivot] + quicksort(Ldroite)

# Les termes suivants le terme initial sont placés dans 2 listes,
# selon qu'ils sont inférieurs ou pas à ce terme initial.
# Ces 2 listes sont de tailles strictement inférieurs à la taille
# de la liste L. On les trie par un appel récursif à la fonction
# quicksort [tri-rapide], et on reforme la liste triée complète
# en concaténant ces 2 listes triées séparées par le pivot.

## Exercice 7 : Médiane

def mediane(L) :
    M = quicksort(L)
    n = len(M)
    if n%2 == 1 :
        return M[(n-1)//2]
    else :
        return (M[n//2-1]+M[n//2])/2

L = [4,3,2,1,2,3,4,5]
assert mediane(L) == 3.
LL = [1,2,3,4]
assert mediane(LL) == 2.5

## Exercice 8 : Tri d'une liste en fonction d'une autre

def tri_couples(L) :
    '''tri d'une liste de couples selon la première coordonnée'''
    n = len(L)
    if n <= 1 :
        return L
    else :
        pivot = L[0][0]
        Lgauche, Ldroite = [], []
        for i in range(1,n) :
            if L[i][0] < pivot :
                Lgauche.append(L[i])
            else :
                Ldroite.append(L[i])
        return quicksort(Lgauche) + [L[0]] + quicksort(Ldroite)

L = [(0,"serpent"), (4,"éléphant"), (8, "araignée"), (1000, "mille-pattes"), (2, "autruche"), (10, "crabe")]
print(tri_couples(L))

##

def tri2(L1,L2) :
    L = []
    for k in range(len(L1)) :
        L.append((L1[k],L2[k]))
    return tri_couples(L)

L1 = (12, 17, 9, 10, 14)
L2 = ("albert", "bernadette", "claire", "delphine", "edouard")

print(tri2(L1,L2))