## Tri par sélection : à chaque i, on place le min de L[i:] en position i.

def tri_par_selection(L):
    n = len(L)
    for i in range(n):
        j = i
        for k in range(i + 1, n):
            if L[k] < L[j]:
                j = k
        L[i], L[j] = L[j], L[i]
    return L

def tri_par_selection_decroissant(L):
    n = len(L)
    for i in range(n):
        j = i
        for k in range(i + 1, n):
            if L[k] > L[j]:
                j = k
        L[i], L[j] = L[j], L[i]
    return L


## Tri par insertion

def insertion(L, i):
    x = L[i]
    j = i
    while j > 0 and L[j - 1] > x:
        L[j] = L[j - 1]
        j = j - 1
    L[j] = x

def tri_par_insertion(L):
    for i in range(1, len(L)):
        insertion(L, i)
    return L


## Tri par comptage

def effectifs(L, n):
    E = (n + 1) * [0]
    for e in L:
        E[e] = E[e] + 1
    return E

def tri_par_comptage(L, n):
    E = effectifs(L, n)
    R = []
    for i in range(n + 1):
        R = R + E[i] * [i]
    return R


## Recherche

def recherche(L, e):
    for i in range(len(L)):
        if L[i] == e:
            return True
    return False

def recherche_par_dichotomie(L, e):
    debut = 0
    fin = len(L) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if L[milieu] == e:
            return True
        elif L[milieu] < e:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return False


## Ordre alphabétique

def plus_petit(chaine1, chaine2):
    alphabet = [chr(k) for k in range(97, 123)]
    i = 0
    while i < len(chaine1) and i < len(chaine2) and chaine1[i] == chaine2[i]:
        i = i + 1
    if i == len(chaine1):
        return True
    if i == len(chaine2):
        return False
    return alphabet.index(chaine1[i]) < alphabet.index(chaine2[i])

def tri_mot(L):
    n = len(L)
    for i in range(n):
        j = i
        for k in range(i + 1, n):
            if plus_petit(L[k], L[j]):
                j = k
        L[i], L[j] = L[j], L[i]
    return L

def plus_grand_anagramme(mot):
    lettres = [c for c in mot]
    tri_mot(lettres)
    lettres.reverse()
    anagramme = ""
    for c in lettres:
        anagramme = anagramme + c
    return anagramme


## Tri rapide (cas de base indispensable pour s'arrêter)

def tri_rapide(L):
    if len(L) <= 1:
        return L
    pivot = L[0]
    petits = []
    grands = []
    for i in range(1, len(L)):
        if L[i] < pivot:
            petits.append(L[i])
        else:
            grands.append(L[i])
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)