Structures de données et algorithmes · Recherche et tri

Tris par comparaison élémentaires

Les tris simples en O(n carré), à bulles, par insertion, par sélection, qui comparent et échangent des paires d'éléments.

Commencer une leçon sur Tris par comparaison élémentaires

À apprendre d'abord

• Tableaux: Un bloc de mémoire contigu à disposition fixe, où n'importe quel index est atteint en temps constant.

Mène à

• Tris diviser-pour-régner: Les tris diviser-pour-régner, tri fusion et tri rapide, qui battent le O(n carré) en découpant le problème.
• Tri sans comparaison: Trier en exploitant une structure connue dans les valeurs elles-mêmes, par dénombrement ou par base, plutôt que par comparaisons.

Notions liées

• Tris diviser-pour-régner: Les tris diviser-pour-régner, tri fusion et tri rapide, qui battent le O(n carré) en découpant le problème.