Tri spaghetti

Pour les articles homonymes, voir Spaghetti (homonymie).

Le Tri spaghetti est un algorithme analogue en temps linéaire inventé par A. K. Dewdney^[1],[2] dans sa chronique du Scientific American pour trier une liste. Cet algorithme trie une séquence d'objet en O(n) de manière stable. Il requiert un processeur parallèle.

Algorithme

Par souci de simplicité, nous nous limitons aux entiers naturel. La méthode est illustrée avec des spaghetti non cuits :

1. Pour chaque nombre x de la liste, obtenez un spaghetti de longueur x.
2. Après avoir eu tous les spaghettis, posez les sur la table en les mettant debout. Mettez votre main en haut de manière à ne plus voir aucun spaghettis, puis descendez votre main. À chaque spaghetti que vous voyez apparaître, vous avez trouvé le plus grand élément des éléments restants et vous pouvez donc le poser sur la table. Répétez l'opération jusqu'à ne plus avoir de spaghettis.

Notes et références

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail des mathématiques