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.
- Tant que la carte précédente est plus petite:
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.