Existe-t-il des algorithmes de tri plus mauvais que le Bogosort (alias Monkey Sort) ?

Question

Ce matin, mes collègues m'ont ramené à l'époque de l'université en discutant des algorithmes de tri. Nous nous sommes souvenus de nos préférés comme StupidSort et l'un d'entre nous était sûr d'avoir vu un algorithme qui était O(n!) . J'ai donc commencé à chercher les "pires" algorithmes de tri que je pouvais trouver.

Nous avons supposé qu'un tri complètement aléatoire serait plutôt mauvais (c'est-à-dire qu'il faut randomiser les éléments - sont-ils dans l'ordre ? non ? randomiser à nouveau), et j'ai cherché et découvert que cela s'appelle apparemment BogoSort, ou Monkey Sort, ou parfois simplement Random Sort .

Dans le pire des cas, Monkey Sort semble avoir une performance de O() une performance optimale de O(n) et une performance moyenne de O(n·n!) .

Quel est l'algorithme de tri actuellement officiellement accepté qui présente la pire performance moyenne de tri (et qui est donc pire que O(n·n!) ) ?

Answer 1

De David Morgan-Mar de la page Algorithmes ésotériques : Le tri de la conception intelligente

Introduction

Intelligent design sort est un algorithme de tri basé sur la théorie du conception intelligente.

Description de l'algorithme

La probabilité que la liste d'entrée originale soit dans l'ordre exact dans lequel elle se trouve est 1/(n !). La probabilité est si faible qu'il est absurde de dire que cela se produit. qu'il est absurde de dire que cela est arrivé par hasard, et que cela doit donc donc avoir été consciemment mis dans cet ordre par un Trieur intelligent. Par conséquent, on peut supposer qu'il a déjà été trié de façon optimale d'une manière qui transcende notre compréhension mortelle naïve de "l'ordre ascendant". Toute tentative de changer cet ordre pour se conformer à nos propres idées préconçues le rendrait en fait moins trié.

Analyse

Cet algorithme est constant en temps, et trie la liste in-place, ne nécessitant aucune mémoire supplémentaire. En fait, il ne nécessite même pas besoin d'aucun de ces trucs informatiques technologiques suspects. Louez le Trieur !

Commentaires

Gary Rogers écrit :

Rendre le tri constant dans le temps nie le pouvoir du Trieur. Le Trieur Trieur existe en dehors du temps, donc le tri est intemporel. Exiger du temps pour valider le tri diminue le rôle du Trieur. Ainsi... ce tri particulier tri est défectueux, et ne peut pas être être attribué à "The Sorter".

Hérésie !

Answer 2

Il y a de nombreuses années, j'ai inventé (mais jamais mis en œuvre) MiracleSort.

Start with an array in memory.
loop:
    Check to see whether it's sorted.
    Yes? We're done.
    No? Wait a while and check again.
end loop

Finalement, les particules alpha qui retournent les bits dans les puces mémoire devraient aboutir à un tri réussi.

Pour une plus grande fiabilité, copiez le réseau dans un endroit blindé, et vérifiez les réseaux potentiellement triés par rapport à l'original.

Alors comment vérifier le tableau potentiellement trié par rapport à l'original ? Il suffit de trier chaque tableau et de vérifier s'ils correspondent. MiracleSort est l'algorithme évident à utiliser pour cette étape.

EDIT : À proprement parler, il ne s'agit pas d'un algorithme, puisque son aboutissement n'est pas garanti. Est-ce que "pas un algorithme" peut être qualifié de "pire algorithme" ?

Answer 3

Bogosort Quantum

Un algorithme de tri qui suppose que l'interprétation des nombreux mondes de la mécanique quantique est correcte :

1. Vérifiez que la liste est triée. Si ce n'est pas le cas, détruisez l'univers.

À la fin de l'algorithme, la liste sera triée dans le seul univers restant. Cet algorithme prend dans le pire des cas Θ(N) et dans le cas moyen θ(1) du temps. En effet, le nombre moyen de comparaisons effectuées est de 2 : il y a 50% de chances que l'univers soit détruit sur le deuxième élément, 25% de chances qu'il soit détruit sur le troisième, et ainsi de suite.

Answer 4

Jingle Sort, comme décrit aquí .

Vous donnez chaque valeur de votre liste à un enfant différent à Noël. Les enfants, étant d'affreux êtres humains, vont comparer la valeur de leurs cadeaux et se trier en conséquence.

Answer 5

Je suis surpris que personne n'ait encore mentionné sleepsort... Ou bien je ne l'ai pas remarqué ? En tout cas :

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

exemple d'utilisation :

./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7

En termes de performances, c'est terrible (surtout le deuxième exemple). Attendre presque 3,5 mois pour trier 2 chiffres, c'est plutôt mauvais.