Publié · en amélioration
Algorithm
Les algorithmes de tri ordonnent les données : tri fusion, tri rapide, tri par tas, stabilité, borne inférieure n log n et tris intégrés aux langages.
Trier consiste à réorganiser des éléments selon un ordre défini : numérique, alphabétique ou chronologique. On distingue les tris par comparaison (tri à bulles, par insertion, par sélection, tri fusion, tri rapide, tri par tas), qui se demandent seulement si un élément précède un autre, et les tris sans comparaison, comme le tri par dénombrement et le tri par base, qui exploitent directement les valeurs entières ou leurs chiffres.
Le tri prépare la recherche dichotomique, la suppression des doublons, la fusion d'intervalles, les classements et bien d'autres traitements, c'est pourquoi il fait partie des premiers algorithmes étudiés. Connaître la borne inférieure Ω(n log n) des tris par comparaison, la différence entre tri stable et tri en place, ainsi que le fonctionnement des tris intégrés, comme Timsort en Python ou l'introsort de la plupart des implémentations de std::sort en C++, aide à faire le bon choix en production comme en entretien.
Pour l'apprendre, déroulez d'abord à la main le tri par insertion, le tri fusion et le tri rapide sur de petits tableaux, puis implémentez le tri fusion et le tri rapide et comparez leurs meilleur, moyen et pire cas. Entraînez-vous ensuite à trier avec des fonctions clés et des comparateurs, et résolvez des problèmes fondés sur le tri, comme la fusion d'intervalles ou le comptage d'inversions.
Le tri fusion coupe l'entrée en deux puis fusionne les moitiés ; le tri rapide partitionne autour d'un pivot. Les deux s'exécutent en O(n log n) en moyenne.
Un tri stable conserve l'ordre d'origine des éléments de clés égales ; un tri en place n'utilise presque pas de mémoire supplémentaire. L'un ou l'autre compte davantage selon la tâche.
Un argument par arbre de décision montre que tout tri par comparaison exige de l'ordre de n log n comparaisons dans le pire cas. Le tri fusion et le tri par tas atteignent cette borne.
Le tri par dénombrement et le tri par base ordonnent des entiers dont la plage ou le nombre de chiffres est limité en temps quasi linéaire, sans comparer les éléments entre eux.
merge_sort coupe la liste en deux, trie chaque moitié récursivement, puis fusionne les deux moitiés triées en prenant toujours le plus petit des deux éléments de tête. En cas d'égalité, l'élément de gauche passe en premier (<=), ce qui rend le tri stable ; il s'exécute en O(n log n) quelle que soit l'entrée. La dernière ligne compare le résultat avec la fonction intégrée sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySix chapitres pour aller de l'installation aux notions essentielles de Tri.
Posez vos questions, partagez votre expérience et échangez vos avis sur Tri.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.