Bogosort vs bogobogosort [fermé]

Pas bogobogosort

La façon dont vous avez implémenté votre bogobogosort, il est en fait plus rapide que bogosort parce que Voici quelques raisons:

1. Après avoir réussi le tri des éléments k, vous vérifiez immédiatement si k+1 sont triés. Cela signifie que si lors dune lecture aléatoire précédente, vous avez mélangé m éléments dans lordre, après avoir trié les deux premiers éléments, vous atteindrez immédiatement m.

   Par exemple, supposons que vous atteigniez 5 cartes et que vous échouiez. Vous mélangez 5 cartes et recommencez à 2. Si ces 5 cartes sont triées, vous atteindrez immédiatement 6 dès que vous aurez mis les 2 premières cartes dans lordre.

2. En raison du point n ° 1, votre bogobogosort est en fait plus rapide que le bogosort car il na besoin que de trier n-1 cartes au lieu de n . Après avoir trié les n-1 cartes, il vérifie lordre des n cartes et peut échouer. Mais en cas déchec, il réorganise les n cartes de sorte quà chaque fois quil trie n-1 cartes, il dispose dun 1/n chance de réussir. Le nombre total de cartes mélangées est donc de l’ordre de (n-1) * (n-1)! * n ce qui se simplifie en (n-1) * n!, par rapport au bogosort qui mélange n * n! cartes.

   Je crois que le même principe sapplique à chaque étape, donc le temps est encore moins que (n-1) * n!. Je ne suis pas sûr du calcul exact, mais en exécutant votre programme, il semble que le bogobogosort fonctionne à peu près en même temps que le bogosort avec une carte en moins. Ie Your_bogobogosort (n) = bogosort (n-1).

Un véritable bogobogosort

Jai réécrit votre fonction bogobogosort comme suit:

unsigned long bogobogosort(int *data, size_t n) { unsigned long c = 0; size_t b = 2; while (1) { if (sorted(data, b)) { if (b == n) break; b++; } else { b = 2; } c += b; shuffle(data, b); } return c; } 

La principale différence ici est quaprès chaque succès où il incrémente b, il remanie le jeu pour empêcher le point n ° 1 ci-dessus de se produire. Avec ce changement, jobtiens un résultat comme celui-ci:

% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds. 

Commentaires

• Selon la description sur Wikipédia, la première partie de bogosort vérifie les commandes data. Si les N premiers éléments sont dans lordre, un bogosort de ces N éléments ne fait pas un seul shuffle. Donc si jai 0 1 2 3 4 6 5 et bogobogosort que je passe de bogosort de 2 à 5 éléments sans mélange, puis mélangez 6 éléments (et revenez à bo gobogosorting 2).
• @pmg Si telle est la définition correcte de bogobogosort, alors il savère plus rapide que bogosort (comme le prouve le programme OP ') . Je ' ne connais pas les origines du bogobogosort mais pour quil " courir jusquà la mort par la chaleur de lunivers " comme revendiqué, cela devrait ressembler davantage au tri que jai écrit.