Worldlex Wiki 
Le tri spaghetti est un algorithme analogique linéaire permettant de trier une séquence d'éléments. Il a été introduit par A.K. Dewdney dans sa chronique du Scientific American . Cet algorithme trie une séquence d'éléments de manière stable, nécessitant un espace mémoire de pile de O ( n ). Il requiert un processeur parallèle, supposé capable de trouver le maximum d'une séquence d'éléments en temps constant ( O ( 1 )).
Algorithme
Par souci de simplicité, supposons que nous triions une liste de nombres naturels . La méthode de tri est illustrée à l'aide de spaghettis crus :
- Pour chaque nombre x de la liste, obtenez une tige de longueur x . (Une méthode pratique pour choisir l'unité consiste à faire correspondre le plus grand nombre m de la liste à une tige de spaghetti complète. Dans ce cas, la tige complète mesure m unités de spaghetti. Pour obtenir une tige de longueur x , cassez une tige en deux de façon à ce qu'un morceau mesure x unités ; jetez l'autre morceau.)
- Une fois que vous avez tous vos spaghettis, prenez-les délicatement dans votre main et posez-les à plat sur la table. Ensuite, pour chaque spaghetti, abaissez votre autre main jusqu'à ce qu'elle rencontre le spaghetti le plus long. Retirez-le et insérez-le au début de la liste de sortie (initialement vide) (ou, de manière équivalente, placez-le dans le dernier emplacement libre du tableau de sortie). Répétez l'opération jusqu'à ce que tous les spaghettis aient été retirés.
Analyse
La préparation des n spaghettis prend un temps linéaire. Déposer les spaghettis sur la table prend un temps constant, O ( 1 ). Ceci est possible car la main, les spaghettis et la table fonctionnent comme un système de calcul entièrement parallèle . Il reste ensuite n spaghettis à retirer ; par conséquent, en supposant que chaque opération de contact et de retrait prenne un temps constant, la complexité temporelle de l'algorithme dans le pire des cas est O ( n ).