#########################################
######## TP informatique bio-spé ########
########        2025-2026        ########
#########################################


#########################################
###### Thème 10 : Méthodes de tri #######
#########################################

## Listes aléatoires pour tester

import random as rd
L = [rd.randint(-1000,1000) for _ in range(10)]

## Effet de bord

# On parle d'effet de bord lorsque l'argument
# d'une fonction est modifié lors de l'exécution
# de cette fonction.

def touchepas(L) :
    M = L[:]
    M[0] = -15
    return M

def touche(L) :
    L[0] = -15

## Q1 : Tri artisanal

def pos_min(L) :
    min = L[0]
    imin = 0
    for i in range(len(L)) :
        if L[i] < min :
            min = L[i]
            imin = i
    return imin

def tri_basique(L) :
    T = []
    M = L[:] # pas d'effet de bord
    while len(M) > 0 :
        i = pos_min(M)
        T.append(M.pop(i))
    return T

## Q2 : Tri par comptage

def multi(L,a) :
    compteur = 0
    for elt in L :
        compteur += (elt == a)
    return compteur

def tri_comptage(L) :
    m = min(L)
    M = max(L)
    T = []
    for a in range(m,M+1) :
        c = multi(L,a)
        T += c*[a]
    return T

## Q3 : Tri-bulle

# sans effet de bord
def permute(L,i,j) :
    M = L[:]
    M[i],M[j] = M[j],M[i]
    return M

def bubblesort(L) :
    n = len(L)
    T = L[:]
    while n > 1 :
        for i in range(n-1) :
            if T[i] > T[i+1] :
                T = permute(T,i,i+1)
        n -= 1
    return T

# avec effet de bord
def permute2(L,i,j) :
    L[i],L[j] = L[j],L[i]

def bubblesort2(L) :
    n = len(L)
    while n > 1 :
        for i in range(n-1) :
            if L[i] > L[i+1] :
                permute2(L,i,i+1)
        n -= 1

## Tri par insertion

# sans effet de bord
def retrograde(L,i) :
    M = L[:]
    while i > 0 and M[i-1]>M[i]:
        permute2(M,i-1,i)
        i -= 1
    return M

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

# avec effet de bord
def retrograde2(L,i) :
    while i > 0 and L[i-1]>L[i]:
        permute2(L,i-1,i)
        i -= 1

def tri_insertion2(L) :
    n = len(L)
    for i in range(1,n) :
        retrograde2(L,i)

## 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)

# On sépare la liste à trier en deux sous-listes
# dont les éléments sont soit inférieurs,
# soit supérieurs à un pivot choisi.
# On trie les sous-listes par appel récursif
# de la fonction quicksort puis on renvoie
# la concaténation des sous-listes triées.

## Médiane d'une série statistique

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

## Tri alphabétique

def tri_couples(L) :
    M = L[:]
    T = []
    n = len(L)
    for _ in range(n) :
        imin = 0
        min = M[0][0]
        for i in range(len(M)) :
            if M[i][0] < min :
                imin = i
                min = M[i][0]
        T.append(M.pop(imin))
    return T

def tri2(L1,L2) :
    assert len(L1) == len(L2)
    L = []
    for i in range(len(L1)) :
        L.append((L1[i],L2[i]))
    T = tri_couples(L)
    T2 = [t[1] for t in T]
    return T2