Trier des cartes

Algo 06

Résumé du cours

On étudie 2 tris classiques:

Tri par sélection
  • Pour chaque carte du tas:
    • Trouver la plus petite carte dans la partie non triée.
    • Échanger cette carte avec la première de la partie non triée.
def indice_mini(tab: list, dep: int) -> int:
    """
    recherche d'indice minimum dans un tableau
    """
    i_mini = dep
    mini = tab[dep]
    for i in range(dep, len(tab)):
        if tab[i] < mini:
            i_mini = i
            mini = tab[i]
    return i_mini


def echanger(tab: list, i: int, j: int) -> None:
    """
    échange de 2 valeurs dans un tableau
    """
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_selection(tab: list) -> None:
    """
    traduction de l'algorithme de tri par sélection
    """
    for i in range(len(tab)):
        i_mini = indice_mini(tab, i)
        echanger(tab, i, i_mini)
Tri par insertion
  • Pour chaque carte du tas:
    • Tant que la carte précédente est plus petite:
      • Échanger cette carte avec la carte en cours.
def inserer(tab: list, j: int) -> None:
    """
    insertion d'un élément dans la partie triée du tableau
    """
    while j-1 >= 0 and tab[j-1] > tab[j]:
        echanger(tab, j-1, j)
        j = j-1

def echanger(tab: list, i: int, j: int) -> None:
    """
    échange de 2 valeurs dans un tableau
    """
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_insertion(tab: list) -> None:
    """
    traduction de l'algorithme de tri par insertion
    """
    for i in range(len(tab)):
        inserer(tab, i)

Il s’agit de deux algorithmes de complexité quadratique.