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

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"?

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.

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.

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.

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)

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

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).

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

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.

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; }
}

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.

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.

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).

Rien ne peut être pire que l'infini.

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.

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 ² ) 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 :)

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.

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.

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);
}

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; }
        }
}

bogosort Double

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

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.

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 (;;);
}

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).

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.