Tri stupide

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Tri stupide
Image illustrative de l'article Tri stupide
Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problème lié Algorithme de tri
Structure des données Liste ou tableau
Temps d'exécution pire-cas Non borné
Complexité algorithmique spatiale

En informatique, le tri stupide, également appelé 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 à mélanger aléatoirement les éléments, puis à répéter l'opération.

 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 un algorithme de Las Vegas.

Complexité[modifier | modifier le code]

Si les éléments sont distincts deux à deux, le nombre de comparaisons moyen est asymptotiquement équivalent à et le nombre de mélanges moyen est égal à [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.