Pourquoi avons-nous besoin de tant de techniques de tri ?

Question

Il existe une pléthore de techniques de tri dans la structure des données, comme suit -
Sélection Tri
Tri à bulles
Tri à bulles récursif
Tri par insertion
Tri par insertion récursif
Fusionner le tri
Triage itératif par fusion
Tri rapide
Tri rapide itératif
Triage en tas
Triage par comptage
Radix Sort
Tri des seaux
Tri des coquillages
Tim Sort
Triage par peigne
Pigeonhole Sort
Tri du cycle
Triage des cocktails
Tri des brins
et bien d'autres encore.
Avons-nous besoin de tous ces éléments ?

Answer 1

Il n'y a pas de raison unique pour laquelle il existe autant d'algorithmes de tri différents. Voici un échantillon d'algorithmes de tri et leur origine, pour vous donner une meilleure idée de leurs origines :

• Le tri par radix a été inventé à la fin des années 1800 pour le tri physique des cartes perforées pour le recensement américain. Il est encore utilisé aujourd'hui dans les logiciels car il est très rapide sur les données numériques et les chaînes de caractères.
• Le tri par fusion semble avoir été inventé par John von Neumann pour valider son modèle d'ordinateur à programme enregistré (l'architecture de von Neumann). Il fonctionne bien comme algorithme de tri pour les ordinateurs à faible mémoire qui traitent des données en continu, d'où sa popularité dans les années 1960 et 1970. Il constitue également un excellent banc d'essai pour les techniques de division et de conquête, ce qui le rend populaire dans les cours d'algorithmique.
• Le tri d'insertion semble exister depuis toujours. Même s'il est lent dans le pire des cas, il est fantastique sur les petites entrées et les données majoritairement triées. Il est utilisé comme élément de base dans d'autres algorithmes de tri rapides.
• Quicksort a été inventé en 1961. Il se joue très bien des caches des processeurs, d'où sa popularité persistante.
• Les réseaux de triage ont été étudiés de manière approfondie il y a de nombreuses années. Ils sont toujours utiles comme blocs de construction dans les algorithmes théoriques de preuve de concept comme le tri par signature.
• Timsort a été inventé pour Python et a été conçu pour trier les séquences pratiques du monde réel plus rapidement que les autres tris en tirant parti des distributions et des modèles communs.
• Introsort a été inventé comme un moyen pratique d'exploiter la vitesse de quicksort sans son comportement de pire cas.
• Shellsort a été inventé il y a plus de cinquante ans et était pratique sur les ordinateurs de son époque. Sonder ses limites théoriques était un problème mathématique difficile pour les personnes qui l'ont étudié à l'époque.
• L'algorithme de tri d'entiers en temps O(n sqrt(log log n)) de Thorup et Yao a été conçu pour sonder les limites théoriques des algorithmes efficaces utilisant le parallélisme au niveau des mots.
• Le tri cyclique découle de l'étude des permutations en théorie des groupes et est conçu pour minimiser le nombre d'écritures en mémoire lors du tri de la liste.
• Heapsort est remarquable pour être in-place et pourtant rapide en pratique. Il est basé sur l'idée de représenter implicitement une structure de données non triviale.

Cette liste d'algorithmes de tri est loin d'être exhaustive, mais elle devrait vous donner une idée de ce qui existe et pourquoi :-)

Answer 2

La principale raison pour laquelle les algorithmes de tri sont discutés et étudiés dans les premiers cours d'informatique est qu'ils constituent un très bon matériel d'étude. Le problème du tri est simple et constitue une bonne excuse pour présenter plusieurs stratégies d'algorithmes, plusieurs structures de données, la manière de les mettre en œuvre, et pour discuter de la complexité temporelle et spatiale, ainsi que des différentes propriétés que peuvent avoir les algorithmes même s'ils résolvent apparemment le même problème.

Dans la pratique, les bibliothèques standard des langages de programmation incluent généralement une fonction par défaut sort comme std::sort en C++ ou list.sort en python ; et dans presque toutes les situations, vous devriez faire confiance à cette fonction et à l'algorithme qu'elle utilise.

Mais tout ce que vous avez appris sur les algorithmes de tri est précieux et peut être appliqué à d'autres problèmes. Voici une liste non exhaustive de ce que l'on peut apprendre en étudiant les algorithmes de tri :

• diviser et conquérir ;
• des tas ;
• arbres de recherche binaires, y compris différents types d'arbres de recherche binaires auto-équilibrés ;
• l'importance de choisir une structure de données appropriée ;
• différence entre en place et non en place ;
• différence entre un tri stable et un tri non stable ;
• approche récursive et approche itérative ;
• comment calculer la complexité temporelle, et comment comparer l'efficacité de deux algorithmes ;

Answer 3

Outre les raisons pédagogiques, nous avons besoin de plusieurs algorithmes de tri parce qu'ils fonctionnent mieux dans quelques situations, et qu'aucun d'entre eux les gouverne tous .

Par exemple, bien que le temps moyen de complexité de quicksort est impressionnante, ses performances sur presque trié Le tableau est horrible.