Bogosort vs bogobogosort [gesloten]

Niet bogobogosort

De manier waarop je je bogobogosort hebt geïmplementeerd, is eigenlijk sneller dan bogosort, omdat een aantal redenen:

1. Nadat je k elementen succesvol hebt bogosort, controleer je onmiddellijk of k+1 elementen worden gesorteerd. Dit betekent dat als je tijdens een vorige shuffle m elementen in willekeurige volgorde hebt geschud, en je, nadat je de eerste twee elementen hebt gesorteerd, onmiddellijk m.

   Stel dat u 5 kaarten bereikt en dan faalt. Je schudt 5 kaarten en begint dan opnieuw bij 2. Als die 5 kaarten toevallig in gesorteerde volgorde staan, bereik je onmiddellijk 6 zodra je de eerste 2 kaarten op volgorde legt.

2. Vanwege punt 1 is je bogobogosort eigenlijk sneller dan de bogosort omdat het alleen n-1 kaarten hoeft te sorteren in plaats van n . Nadat het n-1 kaarten heeft gesorteerd, controleert het de volgorde van n kaarten en kan het mislukken. Maar als dit niet lukt, worden n kaarten opnieuw geschud, zodat elke keer dat het n-1 kaarten sorteert, het een 1/n kans om uiteindelijk te slagen. Het totale aantal geschudde kaarten is dus in de volgorde (n-1) * (n-1)! * n wat vereenvoudigt tot (n-1) * n!, vergeleken met de bogosort die n * n! kaarten.

   Ik geloof dat hetzelfde principe bij elke stap van toepassing is, dus de tijd is zelfs minder dan (n-1) * n!. Ik ben niet zeker van de exacte wiskunde, maar als je je programma uitvoert, blijkt dat de bogobogosort ongeveer in dezelfde tijd wordt uitgevoerd als de bogosort met één kaarten minder. Dat wil zeggen Your_bogobogosort (n) = bogosort (n-1).

Een goede bogobogosort

Ik heb je bogobogosort-functie herschreven om er als volgt uit te zien:

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

Het belangrijkste verschil hier is dat na elk succes waar het b verhoogt, het de stapel opnieuw schudt om te voorkomen dat punt 1 hierboven gebeurt. Met deze wijziging krijg ik de uitvoer als volgt:

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

Reacties

• Volgens de beschrijving op Wikipedia controleert het eerste deel van bogosort op geordende gegevens. Als de eerste N elementen in orde zijn, doet een bogosort van die N elementen geen enkele shuffle. Dus als ik 0 1 2 3 4 6 5 en bogobogosort heb, ga ik van bogosort van 2 naar 5 elementen zonder te schudden, schud dan 6 elementen (en ga terug naar bo gobogosorting 2).
• @pmg Als dat de juiste definitie is van bogobogosort, dan blijkt het sneller te zijn dan bogosort (zoals het OP ' s programma bewijst) . Ik ' ben niet bekend met de oorsprong van bogobogosort, maar om " te laten draaien tot de hitte van het universum " zoals beweerd, het zou meer moeten lijken op het soort dat ik schreef.