# TP 08 correction : Tri
# BCPST1B 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% exercice 1

# classique ! à savoir faire !
def est_croissante(L):
    n = len(L)
    for i in range(n-1):
        if L[i+1] < L[i]:
            return False
    return True

# test
L = [2, 6, 7, 7, 9, 15]
print("L =", L)
print(est_croissante(L))
M = [1, 8, 9, 3, 4, 25]
print("M =", M)
print(est_croissante(M))

#%% exercice 2

def maximum(L):
    n = len(L)
    assert n != 0, "le maximum d'une liste vide n'est pas défini"
    # au départ le maximum supposé ne peut être que
    M = L[0]
    # parcourir la liste
    for i in range(1, n):
        # L[i] est-il le nouveau maximum ?
        if L[i] > M:
            M = L[i]
    return M

# test
L = [10, 1, 5, 6, 7, 5]
print("L =", L)
print(maximum(L))
M = [1, 1, 5, 6, 9, 5]
print("M =", M)
print(maximum(M))
N = [1, 8, 6, 8, 8, 12]
print("N =", N)
print(maximum(N))

#%% exercice 3

def echange(L, i, j):
    t = L[i]
    L[i] = L[j]
    L[j] = t
    return L

# test : les opérations s'enchainent
L = [1, 8, 4, 2, 1, 25]
print("L =", L)
echange(L, 1, 4)
print(L)
echange(L, 2, 3)
print(L)

#%% exercice 4

def tri_bulle(L):
    n = len(L)
    # répéter le bon nombre de fois
    for i in range(n-1):
        # parcourir la liste et ordonner, si nécessaire, deux éléments consécutifs
        # au i-ème passage, les i derniers sont déjà triés...
        for j in range(n-i-1):
            if L[j+1] < L[j]:
                t = L[j]
                L[j] = L[j+1]
                L[j+1] = t
    return L

# test
L = [6, 9, 7, 6, 8, 3, 2, 5]
print("L = ", L)
print(tri_bulle(L))
M = [9, 2, 7, 1, 3, 1, 2, 1]
print("M =", M)
print(tri_bulle(M))
N = [1, 8, 5, 8, 6, 4, 1, 7]
print("N =", N)
print(tri_bulle(N))

#%% exercice 5

def tri_selection(L):
    n = len(L)
    # placer l'élément d'indice i, pour chaque i
    for i in range(n-1):
        # chercher l'indice du minimum de la liste à partir de l'indice i, inclus
        imin = i
        for j in range(i+1, n):
            if L[j] < L[imin]:
                imin = j
        # échanger les éléments d'indices i et imin
        t = L[i]
        L[i] = L[imin]
        L[imin] = t
    return L

# test
L = [6, 9, 7, 6, 8, 3, 2, 5]
print("L = ", L)
print(tri_selection(L))
M = [9, 2, 7, 1, 3, 1, 2, 1]
print("M =", M)
print(tri_selection(M))
N = [1, 8, 5, 8, 6, 4, 1, 7]
print("N =", N)
print(tri_selection(N))

#%% exercice 6

def tri_insertion(L):
    n = len(L)
    # répéter : prendre l'élément d'indice i et l'insérer à sa place parmi les i premiers éléments
    for i in range(1, n):
        x = L[i]
        # pour tous les éléments d'indice de i-1 à 0 (boucle décroissante) tant qu'ils sont plus grands que x
        j = i - 1
        while j >= 0 and L[j] > x:
            # échanger les éléments d'indice j et j+1
            # en fait, on décale tous les éléments puis on insère x
            L[j+1] = L[j]
            j = j - 1
        L[j+1] = x
    return L

# test
L = [6, 9, 7, 6, 8, 3, 2, 5]
print("L = ", L)
print(tri_insertion(L))
M = [9, 2, 7, 1, 3, 1, 2, 1]
print("M =", M)
print(tri_insertion(M))
N = [1, 8, 5, 8, 6, 4, 1, 7]
print("N =", N)
print(tri_insertion(N))

#%% exercice 7

# import ?
from random import randrange

def tri_stupide(L):
    n = len(L)
    # tant que ce n'est pas fini
    while not est_croissante(L):
        # choisir des indices au hasard
        i = randrange(n)
        j = randrange(n)
        # échanger s'ils ne sont pas dans le bon sens
        if (i < j and L[i] > L[j]) or (i > j and L[i] < L[j]):
            x = L[i]
            L[i] = L[j]
            L[j] = x
    return L

L = [6, 9, 7, 6, 8, 3, 2, 5]
print("L = ", L)
print(tri_stupide(L))
M = [9, 2, 7, 1, 3, 1, 2, 1]
print("M =", M)
print(tri_stupide(M))
N = [1, 8, 5, 8, 6, 4, 1, 7]
print("N =", N)
print(tri_stupide(N))

#%% bonus
# rajouter des print dans la boucle (créer une fonction tri_stupide_print) et observer le comportement avec des listes de plus en plus grandes

from random import randint, randrange

def tri_stupide_print(L):
    n = len(L)
    # tant que ce n'est pas fini
    while not est_croissante(L):
        # choisir des indices au hasard
        i = randrange(n)
        j = randrange(n)
        # échanger s'ils ne sont pas dans le bon sens
        if (i < j and L[i] > L[j]) or (i > j and L[i] < L[j]):
            print(L)
            x = L[i]
            L[i] = L[j]
            L[j] = x
    return L

N = 30 # faire varier
# liste aléatoire de N nombres pris entre 1 et 100
L = [randint(1, 100) for _ in range(N)]
print("L =", L)
tri_stupide_print(L)

#%% exercice 8.1

# classique ! à savoir faire !
def compte(L, N):
    assert all(0 <= x and x <= N for x in L)
    n = len(L)
    C = [0] * (N+1)
    for i in range(n):
        x = L[i]
        C[x] = C[x] + 1
    return C

# test
L = [4, 2, 1, 5, 8, 9, 6, 5, 3, 7, 6, 3, 5, 4, 0, 2, 8, 3, 3, 4]
print("L =", L)
C = compte(L, 9)
print(C)
for x in range(10):
    print("Nombre de", x, " :", C[x])

#%% exercice 8.2

def tri_comptage(L):
    N = maximum(L)
    C = compte(L, N)
    M = []
    # recontruire la liste dans l'ordre :
    for x in range(N+1):
        # M.append consécutifs
        for i in range(C[x]):
            M.append(x)
    return M

# test
L = [4, 2, 1, 5, 8, 9, 6, 5, 3, 7, 6, 3, 5, 4, 0, 2, 8, 3, 3, 4]
print("L =", L)
print(tri_comptage(L))

#%% exercice 9

def mediane_1(L):
    n = len(L)
    M = tri_comptage(L)
    # quand la liste est triée, la médiane est le nombre au milieu !
    # si le nombre d'éléments est pair, on choisit celui au milieu du côté gauche
    return M[(n-1)//2]

def mediane_2(L):
    n = len(L)
    N = maximum(L)
    C = compte(L, N)
    # accumulateurs pour le nombre d'éléments, et pour la position dans la liste
    S = 0
    j = 0
    while 2 * S < n:
        S = S + C[j]
        j = j + 1
    return j - 1

# test
L = [8, 14, 9, 10, 0, 9, 6, 8, 9, 6, 9, 2, 7, 12, 13, 6, 7, 10, 2, 11, 8, 14, 8, 11, 10, 8, 6, 14, 6, 8, 0, 8, 12, 0, 6, 8, 6, 4, 0, 8, 9, 8, 0, 6, 8, 8, 17, 13, 12, 8]
print("L =", L)
print(mediane_1(L))
print(mediane_2(L))