Y a-t-il des algorithmes de tri plus mauvais que Bogosort (A. K. une sorte de singe)? [fermé]

mes collègues m'ont ramené dans le temps à l'époque de L'université avec une discussion sur les algorithmes de tri ce matin. Nous nous sommes souvenus de nos favoris comme StupidSort , et l'un de nous était sûr que nous avions vu un algorithme de tri qui était O(n!) . Ça m'a fait chercher les "pires" algorithmes de tri que j'ai pu trouver.

nous avons postulé qu'un tri complètement aléatoire serait assez mauvais (c. - à-d. randomiser les éléments- est-il dans l'ordre? pas? randomize again), et j'ai regardé autour de moi et j'ai découvert que c'est apparemment appelé BogoSort, ou sorte de singe, ou parfois juste un Sort aléatoire .

Monkey Sort semble avoir une performance du pire des cas de O(∞) , une performance du meilleur des cas de O(n) , et une performance moyenne de O(n·n!) .

y a-t-il des algorithmes nommés qui ont des performances moyennes inférieures à O(n·n!) ? Ou sont tout simplement stupide que le Singe de Tri en général?

152
demandé sur womp 2010-04-09 22:24:09

26 réponses

à Partir de David Morgan-Mar Ésotérique Algorithmes de page: l'Intelligent Design Tri

Introduction

Intelligent design sort est un algorithme de tri basé sur la théorie de l'intelligent design.

Description De L'Algorithme

la probabilité de la liste d'entrée originale étant dans l'ordre exact il est 1 / (n!). Il y a tellement peu de chances que ce soit évidemment absurde de dire que c'est arrivé par hasard, il doit avoir consciemment mis en ordre par un intelligent Trieur. Donc il est raisonnable de supposer qu'il est déjà trié de façon optimale d'une certaine façon cela transcende notre naïve compréhension mortelle de "l'ordre ascendant". Toute tentative de modifier cet ordre pour se conformer à nos propres idées préconçues serait en fait rendre moins triés.

analyse

cet algorithme est constant dans le temps, et trie la liste en place, nécessitant pas de mémoire supplémentaire. En fait, il n'a même pas j'ai besoin de tout ce truc informatique suspect. Louer le Trieur!

"151930920 de" Feedback

Gary Rogers écrit:

Faire le tri constante dans le temps nie le pouvoir de la trieuse. Le Trieur existe en dehors du temps, donc le tri est intemporel. À besoin de temps pour valider la sorte affaiblit le rôle de la Trieuse. Ainsi... ce particulier le tri est imparfait, et ne peut pas être attribué à "la trieuse".

hérésie!

406
répondu BioGeek 2015-04-24 10:31:36

il y a de nombreuses années, J'ai inventé (mais jamais réellement mis en œuvre) le 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

éventuellement, particules alpha retournant des bits dans les puces Mémoire devrait entraîner un tri réussi.

pour plus de fiabilité, Copiez le tableau à un endroit protégé, et vérifiez les tableaux potentiellement triés par rapport à l'original.

alors comment vérifier le tableau potentiellement trié par rapport à l'original? Il suffit de trier chacun tableau et vérifier qu'elles correspondent. MiracleSort est l'algorithme évident à utiliser pour cette étape.

EDIT: Strictement parlant, ce n'est pas un algorithme, puisqu'il n'est pas garanti à la fin. Ne pas "un algorithme de" qualifier "un pire algorithme"?

274
répondu Keith Thompson 2013-02-21 18:16:54

Bogosort Quantique

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

  1. Vérifier que la liste est triée. Si pas, de détruire l'univers.

À la fin de l'algorithme, la liste sera triée dans le seul univers qui reste debout. Cet algorithme prend le pire des cas O( N) et moyenne-case O (1) Temps. En fait, le nombre moyen de comparaisons effectuées est de 2: il y a 50% de chance que l'univers soit détruit sur le deuxième élément, 25% de chance qu'il soit détruit sur le troisième, et ainsi de suite.

125
répondu BioGeek 2010-04-09 19:46:09

Jingle Sort, comme décrit ici .

vous donnez chaque valeur de votre liste à un enfant différent à Noël. Les enfants, étant des êtres humains horribles, compareront la valeur de leurs dons et se trient en conséquence.

53
répondu Curtis Lassam 2013-06-08 02:07:26

je suis surpris que personne n'ait encore mentionné sleepsort... Ou n'ai-je pas remarqué? Quoi qu'il en soit:

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

exemple d'usage:

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

En termes de performance, il est terrible (surtout le deuxième exemple). Attendre près de 3,5 mois pour trier 2 nombres est un peu mauvais.

52
répondu Kw4s 2012-11-30 11:08:17

j'ai eu un conférencier qui a un jour suggéré de générer un tableau aléatoire, en vérifiant s'il était trié et puis en vérifiant si les données étaient les mêmes que le tableau à trier.

dans le Meilleur des cas O(N) (première fois de bébé!) Pire des cas O(Jamais)

43
répondu Daniel 2010-04-19 04:18:50

si vous gardez l'algorithme significatif de quelque manière que ce soit, O(n!) est la pire limite supérieure que vous pouvez atteindre.

puisque vérifier chaque possibilité pour une permutations d'un ensemble à trier va prendre n! pas, vous ne pouvez pas obtenir pire que cela.

Si vous faites plus d'étapes qu'alors que l'algorithme n'a pas de réelle utilité. Sans parler de l'algorithme de tri simple suivant avec O(infinity) :

list = someList
while (list not sorted):
    doNothing
29
répondu Yuval Adam 2010-04-09 18:26:46

Vous devriez faire de la recherche dans le domaine passionnant de l' Pessimal Algorithmes et Simplexity Analyse . Ces auteurs travaillent sur le problème du développement d'une sorte avec un meilleur cas pessimiste (le meilleur cas de votre bogosort est Omega(n), tandis que slowsort (voir papier) a une complexité de temps de meilleur cas non-polynomial).

17
répondu Derrick Turk 2016-11-04 19:17:06

voici deux sortes j'ai trouvé mon colocataire à la fac

1) Vérifier la commande 2) peut-être qu'un miracle est arrivé, passez à 1

et

1) vérifiez si elle est en ordre, sinon 2) Mettez chaque élément dans un paquet et renvoyez-le d'un serveur distant à vous-même. Certains de ces paquets reviendront dans un ordre différent, donc passez à 1

16
répondu Seth 2012-07-16 21:55:45

Bogobogosort. Oui, c'est une chose. à Bogobogosort, vous Bogosort le premier élément. Vérifiez si cet élément est trié. Étant un élément, il sera. Ensuite, vous ajoutez le deuxième élément, et Bogosort ces deux jusqu'à ce qu'il soit trié. Puis vous ajoutez un élément de plus, puis Bogosort. Continuez à ajouter des éléments et à Bogosorter jusqu'à ce que vous ayez finalement fait chaque élément. Cela a été conçu pour ne jamais réussir avec une liste de taille avant la mort de la chaleur de l'univers.

15
répondu Playnwinplayer 2013-07-12 01:30:36

il y a toujours le Bogobogosort (Bogoception!). Il exécute Bogosort sur des sous-ensembles de plus en plus grands de la liste, puis recommence tout à nouveau si la liste n'est jamais triée.

for (int n=1; n<sizeof(list); ++n) {
  while (!isInOrder(list, 0, n)) {
    shuffle(list, 0, n);
  }
  if (!isInOrder(list, 0, n+1)) { n=0; }
}
13
répondu IceMetalPunk 2013-06-01 23:28:59

il y a une sorte qui s'appelle bogobogosort. Tout d'abord, il vérifie les 2 premiers éléments, et bogosorts. Ensuite, il vérifie les 3 premiers, bogosorts, et ainsi de suite. Si la liste est hors service à tout moment, elle redémarre en bogosortant les 2 premiers. Bogosort régulier a une complexité moyenne de O (N!), cet algorithme a une complexité moyenne de O (N!1!2!3!...N!) Edit: pour vous donner une idée de la taille de ce nombre, pour 20 éléments, cet algorithme prend une moyenne de 3.930093*10^158 les années, bien au-dessus de la mort de chaleur proposée de l'univers(si elle se produit) de 10^100 ans, tandis que la sorte de fusion prend autour .0000004 secondes, le tri à bulles .0000016 secondes, et bogosort prend 308 ans, 139 jours, 19 heures, 35 minutes, 22.306 secondes, en supposant une année est 365.242 jours et un ordinateur ne 250,000,000 un entier de 32 bits par seconde. Edit2: cet algorithme n'est pas aussi lent que le sort miracle "algorithme", qui probablement, comme ce sort, va faire aspirer l'ordinateur dans le trou noir avant de trier avec succès 20 éléments, mais si c'était le cas, j'estimerais une complexité moyenne de 2^(32(le nombre de bits dans un entier de 32 bits) N)(Le nombre d'éléments) (un nombre <=10^40 ans, car la gravité accélère le déplacement des puces alpha, et il y a 2^n États, qui est 2^640*10^40, soit environ 5.783*10^216.762162762 années, bien que si la liste a commencé triée, sa complexité serait seulement O (N), plus rapide que le tri de fusion, qui est seulement n log n Même au pire cas. Edit3: cet algorithme est en fait plus lent que miracle sort car la taille devient très grande, disons 1000, puisque mon algorithme aurait un temps d'exécution de 2,83*10^1175546 années, tandis que l'algorithme miracle sort aurait un temps d'exécution de 1,156*10^9657 années.

11
répondu bacca2002 2014-07-24 03:43:20

1 Placez vos articles pour être triés sur les cartes d'index

2 jetez-les en l'air par temps venteux, à 1,5 km de votre maison.

2 jetez-les dans un feu de joie et confirmez qu'ils sont entièrement détruits.

3 Vérifiez le plancher de votre cuisine pour la commande correcte.

4 Répétez si ce n'est pas le bon ordre.

dans le Meilleur des cas scenerio est O(∞)

Edit ci-dessus basé sur l'observation astucieuse de KennyTM.

9
répondu Patrick Karcher 2010-04-09 18:53:29

Le "que voudrais-tu qu'il soit?"trier

  1. noter l'heure du système.
  2. triez à L'aide de Quicksort (ou de toute autre méthode raisonnable), en omettant le tout dernier échange.
  3. noter l'heure du système.
  4. calculer le temps requis. L'arithmétique de précision étendue est une exigence.
  5. attendre le temps requis.
  6. effectuer le dernier échange.

non seulement il peut mettre en œuvre n'importe quelle valeur o(x) concevable court de l'infini, le temps pris est provably correct (si vous pouvez attendre aussi longtemps).

9
répondu david.pfx 2014-03-11 11:01:05

Rien ne peut être pire que l'infini.

7
répondu Joseph Salisbury 2010-04-09 18:26:34

Bozo sort est un algorithme apparenté qui vérifie si la liste est triée et, si non, échange deux éléments au hasard. Il a les mêmes performances de meilleur et de pire cas, mais je m'attends intuitivement à ce que le cas Moyen soit plus long que Bogosort. Il est difficile de trouver (ou de produire) des données sur les performances de cet algorithme.

5
répondu tloflin 2010-04-09 18:57:44

une performance du pire des cas de O(∞) pourrait même ne pas en faire un algorithme selon certains .

Un algorithme est une série d'étapes et vous pouvez toujours faire pire en peaufinant un peu pour obtenir le résultat souhaité, en plus de pas que c'était déjà prise. On pourrait délibérément mettre la connaissance du nombre d'étapes prises dans l'algorithme et le faire terminer et produire la sortie correcte seulement après X nombre de des mesures ont été fait. X pourrait très bien être de l'ordre de O(n 2 ) ou O(n n! ) ou quel que soit l'algorithme désiré faire. Cela aurait pour effet d'augmenter les limites de son meilleur cas ainsi que la moyenne des cas.

Mais votre pire scénario ne peut pas être surmontée :)

4
répondu Anurag 2010-04-09 18:39:45

Segments de π

supposons que π contient toutes les combinaisons possibles de nombres finis. Voir "151950920 des mathématiques".stackexchange question

  1. déterminer le nombre de chiffres nécessaires à partir de la taille du tableau.
  2. utilise des segments de π places comme index pour déterminer comment ré-ordonner le tableau. Si un segment dépasse les limites de taille pour ce tableau, ajustez le décalage décimal π et recommencer.
  3. vérifier si le tableau ré-commandé est trié. S'il est woot, autrement ajuster l'offset et recommencer.
4
répondu CrashCodes 2017-04-13 12:19:15

mon algorithme de tri lent préféré est le tri stooge:

void stooges(long *begin, long *end) {
   if( (end-begin) <= 1 ) return;
   if( begin[0] < end[-1] ) swap(begin, end-1);
   if( (end-begin) > 1 ) {
      int one_third = (end-begin)/3;
      stooges(begin, end-one_third);
      stooges(begin+one_third, end);
      stooges(begin, end-one_third);
   }
}

le pire cas de complexité est O(n^(log(3) / log(1.5))) = O(n^2.7095...) .

un autre algorithme de tri lent s'appelle en fait slowsort!

void slow(long *start, long *end) {
   if( (end-start) <= 1 ) return;
   long *middle = start + (end-start)/2;
   slow(start, middle);
   slow(middle, end);
   if( middle[-1] > end[-1] ) swap(middle-1, end-1);
   slow(start, end-1);
}

celui-ci "prend 151930920" dans le meilleur des cas... même plus lent que stoogesort.

3
répondu Ben Goldberg 2011-11-01 19:37:23
Recursive Bogosort (probably still O(n!){
if (list not sorted)
list1 = first half of list.
list 2 = second half of list.
Recursive bogosort (list1);
Recursive bogosort (list2);
list = list1 + list2
while(list not sorted)
    shuffle(list);
}
3
répondu user3667082 2014-05-23 00:07:51

cette page est une lecture intéressante sur le thème: http://home.tiac.net/~cri_d/cri/2001/badsort.html

mon préféré est le sillysort de Tom Duff:

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}
2
répondu fsanches 2012-11-25 07:12:14

bogosort Double

Bogosort deux fois et comparer les résultats (juste pour être sûr qu'il est trié) si pas le faire à nouveau

2
répondu Viktor Mellgren 2013-05-30 20:22:50

vous pouvez rendre n'importe quel algorithme de tri plus lent en lançant votre étape "est-il trié" au hasard. Quelque chose comme:

  1. créez un tableau de booléens de la même taille que le tableau que vous triez. Réglez-les tous pour de faux.
  2. exécuter une itération de bogosort
  3. choisir deux éléments aléatoires.
  4. Si les deux éléments sont triés par rapport à eachother (i < j && tableau[i] < tableau[j]), marque l'index des deux sur le tableau booléen à true. Overwise, recommencer.
  5. vérifiez si tous les booléens du tableau sont vrais. Sinon, retournez à la 3.
  6. fait.
1
répondu Brendan Long 2010-04-09 19:29:35

Oui, SimpleSort, en théorie, il s'exécute en O(-1) cependant, cela est est équivalent à O(...9999) , ce qui est équivalent à O(∞ - 1), qui, comme il arrive, c'est aussi équivalent à O(∞). Voici mon exemple d'implémentation:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}
1
répondu Joe D 2010-08-29 19:25:37

un que je viens de travailler sur implique de choisir deux points aléatoires, et s'ils sont dans le mauvais ordre, en inversant le sous-rang entier entre eux. J'ai trouvé l'algorithme sur http://richardhartersworld.com/cri_d/cri/2001/badsort.html , qui dit que le cas moyen est probablement quelque part autour de O(N^3) ou O(N^2 log n) (Il n'est pas vraiment sûr).

je pense qu'il pourrait être possible de le faire plus efficacement, parce que je pense qu'il pourrait être possible de faire l'opération d'inversion en O (1) Temps.

en fait, je viens de réaliser que faire cela ferait peut-être toute la chose que je dis peut-être parce que je viens de réaliser que la structure de données que j'avais en tête mettrait l'accès aux éléments aléatoires à o(log n) et de déterminer si elle a besoin d'Inverser à O(n).

1
répondu AJMansfield 2013-03-14 01:40:54

Randomsubsetsort.

étant donné un tableau d'éléments n, choisissez chaque élément avec une probabilité 1/n, Randomisez ces éléments, et vérifiez si le tableau est trié. Répétez jusqu'à ce que triées.

le temps Prévu est laissé comme exercice pour le lecteur.

1
répondu Steven Armstrong 2013-10-19 00:38:21