Tri stupide

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èmes liés	Algorithme de tri, Algorithme de Las Vegas
Structure des données	Tableau

Complexité en temps

Pire cas	${\displaystyle \infty }$[1]
Moyenne	${\displaystyle O((n+1)!)}$[1]
Meilleur cas	${\displaystyle O(n)}$[1]

Complexité en espace

Pire cas	${\displaystyle O(n)}$[1]

modifier - modifier le code - modifier 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

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, puis à recommencer autant de fois que nécessaire.

 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é

Si tous les éléments sont distincts deux à deux, il y a ${\displaystyle n!}$ façons différentes de ranger ${\displaystyle n}$ éléments distincts dans une liste. Nous avons donc ${\displaystyle 1/n!}$ 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 à ${\displaystyle (e-1)n!}$ et le nombre moyen de mélanges est égal à ${\displaystyle (n-1)n!}$^[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

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l'informatique théorique