Tri stupide

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Tri stupide
Bogo sort animation.gif
Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.
Problèmes liés
Structure des données
Complexité en temps
Pire cas
[1]Voir et modifier les données sur Wikidata
Moyenne
[1]Voir et modifier les données sur Wikidata
Meilleur cas
[1]Voir et modifier les données sur Wikidata
Complexité en espace
Pire cas
[1]Voir et modifier les données sur Wikidata

En informatique, le tri stupide, également appelé tri du singe ou bogo-tri ou bogosort, est un algorithme de tri particulièrement inefficace. Il est présenté pour des raisons pédagogiques, par comparaison aux méthodes de tri traditionnelles, ou comme exercice.

Algorithme[modifier | modifier le code]

Le tri stupide consiste à vérifier si les éléments sont ordonnés et s'ils ne le sont pas à les mélanger aléatoirement les éléments, puis à recommencer.

 fonction tri_stupide (liste)
    tant que la liste n'est pas triée
        mélanger aléatoirement les éléments de la liste

L'algorithme est probabiliste, plus précisément c'est un algorithme de Las Vegas.

Complexité[modifier | modifier le code]

Si tous les éléments sont distincts deux à deux, il y a façons différentes de ranger éléments distincts dans une liste. Nous avons donc chance qu'une itération donnée de la boucle trie la liste.

Cet algorithme fait essentiellement deux types d'opérations : des comparaisons et des mélanges; Si les éléments sont distincts deux à deux, le nombre moyen de comparaisons est asymptotiquement équivalent à et le nombre moyen de mélanges est égal à [2].

Le pire cas n'est pas borné, pour la même raison qu'une pièce de monnaie peut tomber arbitrairement longtemps sur pile, mais la probabilité qu'il survienne est nulle. Cependant, le temps d'exécution moyen est fini, selon la même conclusion que celle du paradoxe du singe savant.

Références[modifier | modifier le code]

  1. a b c et d (en) Hermann Gruber, Markus Holzer et Oliver Ruepp, « Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms », Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007. Proceedings, Springer Science+Business Media,‎ , p. 183-197 (DOI 10.1007/978-3-540-72914-3_17)Voir et modifier les données sur Wikidata
  2. H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.