IMG_0362.jpeg

# Algorithmes de tri ## Tri par insertion Principe: comme pour ordonner une main de cartes. On prend les éléments un par un et on les insère à leur place. ```python def tri_insertion(tableau): for i in range(1, len(tableau)): element_a_inserer = tableau[i] j = i # Dép...

# Algorithmes de tri ## Tri par insertion Principe: comme pour ordonner une main de cartes. On prend les éléments un par un et on les insère à leur place. ```python def tri_insertion(tableau): for i in range(1, len(tableau)): element_a_inserer = tableau[i] j = i # Déplacer les éléments du tableau[0..i-1], # qui sont plus grands que element_a_inserer, # d'une position vers l'avant de leur position actuelle while j > 0 and tableau[j-1] > element_a_inserer: tableau[j] = tableau[j-1] j -= 1 tableau[j] = element_a_inserer ``` Complexité: $O(n^2)$. ## Tri rapide (Quick sort) Principe: on choisit un élément appelé pivot. On réarrange le tableau de sorte que tous les éléments plus petits que le pivot soient placés avant le pivot, et tous les éléments plus grands après. On trie ensuite récursivement les deux sous-tableaux. ```python def partitionner(tableau, debut, fin): pivot = tableau[debut] gauche = debut+1 droite = fin while True: while gauche = pivot: droite -= 1 while gauche 1: milieu = len(tableau) // 2 gauche = tableau[:milieu] droite = tableau[milieu:] tri_fusion(gauche) tri_fusion(droite) i = j = k = 0 while i < len(gauche) and j < len(droite): if gauche[i] < droite[j]: tableau[k] = gauche[i] i += 1 else: tableau[k] = droite[j] j += 1 k += 1 while i < len(gauche): tableau[k] = gauche[i] i += 1 k += 1 while j < len(droite): tableau[k] = droite[j] j += 1 k += 1 ``` Complexité: $O(n \log n)$.