Tri stupide

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, le tri stupide, également appelé bogo-tri ou bogosort, est un algorithme de tri dont la particularité est d'être inefficace. Il est utilisé 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 à mélanger aléatoirement les éléments, puis à répéter l'opération.

Complexité[modifier | modifier le code]

Cet algorithme est probabiliste par nature. Si chaque élément est distinct, le nombre de comparaisons moyen est asymptotiquement équivalent à (e-1) n! et le nombre de mélanges moyen est égal à (n-1) n![1].

Le pire cas n'est pas borné, pour la même raison qu'une pièce de monnaie peut tomber une infinité de fois de suite sur pile ou sur face. Cependant, le temps d'exécution est supposé fini quelle que soit la taille de l'ensemble à trier, selon la même conclusion que le paradoxe du singe savant.

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

  1. 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.