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[modifier | modifier le code]
Par souci de simplicité, nous nous limitons aux entiers naturel. La méthode est illustrée avec des spaghetti non cuits :
- Pour chaque nombre x de la liste, obtenez un spaghetti de longueur x.
- 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[modifier | modifier le code]
- Alexander Dewdney, On the spaghetti computer and other analog gadgets for problem solving, Scientific American, vol. 250 no. 6, pages 19-26
- Andrew Adamatzky, From Utopian to Genuine Unconventional Computers, Luniver Press, page 96, (ISBN 0-9551170-9-7)
