Tri stupide
- Tri stupide
-
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
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é
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
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Tri stupide de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Stupide — Intelligence Psychologie Approches et courants Psychodynamique • Humanisme • … Wikipédia en Français
TEMPS — Chacun sait à quel aspect de son expérience répond le mot de temps; mais aucune définition de la notion correspondante n’a reçu jusqu’ici, chez les savants comme chez les philosophes, une approbation unanime. Sensible à cette difficulté qu’il… … Encyclopédie Universelle
Animaux Dans Les Simpsons — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Animaux dans Les Simpson — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Animaux dans Les Simpsons — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Animaux dans les Simpson — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Animaux dans les simpsons — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Asa Phelps — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Bernice Hibbert — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
Chef Wiggum — Liste des personnages des Simpson Les personnages des Simpson présentent une importante diversité, avec en premier plan la famille Simpson : Homer, père de famille aimant et amoureux mais également fainéant, inconscient, stupide et immature … Wikipédia en Français
