Explication des algorithmes de tri

Les algorithmes de tri sont un ensemble d'instructions qui prennent un tableau ou une liste comme entrée et organisent les éléments dans un ordre particulier.

Les tri sont le plus souvent en ordre numérique ou alphabétique (appelé lexicographique), et peuvent être en ordre croissant (AZ, 0-9) ou décroissant (ZA, 9-0).

Pourquoi les algorithmes de tri sont importants

Étant donné que le tri peut souvent réduire la complexité d'un problème, il s'agit d'un algorithme important en informatique. Ces algorithmes ont des applications directes dans les algorithmes de recherche, les algorithmes de base de données, les méthodes de division et de conquête, les algorithmes de structure de données et bien d'autres.

Quelques algorithmes de tri courants

Certains des algorithmes de tri les plus courants sont:

  • Tri par sélection
  • Tri à bulles
  • Tri par insertion
  • Tri par fusion
  • Tri rapide
  • Tri de tas
  • Tri de comptage
  • Tri Radix
  • Tri de seau

Classification de l'algorithme de tri

Les algorithmes de tri peuvent être classés en fonction des paramètres suivants:

  1. Basé sur le nombre de swaps ou d'inversion Il s'agit du nombre de fois où l'algorithme échange des éléments pour trier l'entrée. Selection Sortnécessite le nombre minimum de swaps.
  2. Basé sur le nombre de comparaisons Il s'agit du nombre de fois où l'algorithme compare des éléments pour trier l'entrée. En utilisant la notation Big-O, les exemples d'algorithmes de tri énumérés ci-dessus nécessitent au moins des O(nlogn)comparaisons dans le meilleur des cas et des O(n^2)comparaisons dans le pire des cas pour la plupart des sorties.
  3. Basé sur la récursivité ou la non-récursivité Certains algorithmes de tri, tels que Quick Sort, utilisent des techniques récursives pour trier l'entrée. D'autres algorithmes de tri, tels que Selection Sortou Insertion Sort, utilisent des techniques non récursives. Enfin, certains algorithmes de tri, tels que Merge Sort, utilisent à la fois des techniques récursives et non récursives pour trier l'entrée.
  4. On dit stableque les algorithmes de tri sont basés sur la stabilité si l'algorithme maintient l'ordre relatif des éléments avec des clés égales. En d'autres termes, deux éléments équivalents restent dans le même ordre dans la sortie triée qu'ils l'étaient dans l'entrée.
  5. Insertion sort, Merge Sortet Bubble Sortsont stables
  6. Heap Sortet Quick Sortne sont pas stables
  7. Basé sur un espace supplémentaire requis, les algorithmes de tri sont censés être in placeutilisés s'ils nécessitent un O(1)espace supplémentaire constant pour le tri.
  8. Insertion sortet Quick-sortsont in placetriés lorsque nous déplaçons les éléments autour du pivot et n'utilisons pas réellement un tableau séparé, ce qui n'est PAS le cas dans le tri par fusion où la taille de l'entrée doit être allouée au préalable pour stocker la sortie pendant le tri.
  9. Merge Sortest un exemple de out placetri car il nécessite un espace mémoire supplémentaire pour ses opérations.

Meilleure complexité temporelle possible pour tout tri basé sur une comparaison

Tout algorithme de tri basé sur une comparaison doit effectuer au moins des comparaisons nLog2n pour trier le tableau d'entrée, et le tri Heapsort et le tri par fusion sont des tri de comparaison asymptotiquement optimaux. Cela peut être facilement prouvé en dessinant le diagramme d'arbre de décision.