Bogosort vs bogobogosort [stängt]

Inte bogobogosort

Hur du implementerade din bogobogosort är det faktiskt snabbare än bogosort becau se av några anledningar:

1. När du lyckats bogosortera k -element, kontrollerar du omedelbart om k+1 element sorteras. Det betyder att om du på en tidigare blandning råkar blanda m element i ordning, kommer du omedelbart att nå m.

   Antag till exempel att du når fem kort och sedan misslyckas. Du blandar 5 kort och börjar sedan om 2. Om dessa 5 kort råkar vara i sorterad ordning når du omedelbart 6 så snart du ordnar de två första korten.

2. På grund av punkt 1 är din bogobogosort faktiskt snabbare än bogosorten eftersom den bara behöver sortera n-1 -kort istället för n . När det har sorterat n-1 -kort kontrollerar det ordningen på n -kort och kan misslyckas. Men om det misslyckas, blandar det om n -kort så att varje gång det sorterar n-1 -kort har det ett 1/n chans att så småningom lyckas. Så det totala antalet kort som blandas är i storleksordningen (n-1) * (n-1)! * n vilket förenklar till (n-1) * n!, jämfört med bogosorten som blandar n * n! -kort.

   Jag tror att samma princip gäller i varje steg, så tiden är ännu mindre än (n-1) * n!. Jag är inte säker på den exakta matematiken, men från att köra ditt program verkar det som om bogobogosort körs ungefär samma tid som bogosort med ett kort färre. Det vill säga Your_bogobogosort (n) = bogosort (n-1).

En ordentlig bogobogosort

Jag skrev om din bogobogosort-funktion för att vara så här:

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

Huvudskillnaden här är att det efter varje framgång där det ökar b, blandar det om däcket för att förhindra att punkt 1 ovan inträffar .. Med denna förändring får jag output så här:

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

Kommentarer

• Enligt beskrivningen på Wikipedia kontrollerar den första delen av bogosort efter beställning data. Om de första N-elementen är i ordning gör en bogosort av dessa N-element inte en enda blandning. Så om jag har 0 1 2 3 4 6 5 och bogobogosort så går jag från bogosort från 2 till 5 element utan att blanda, blanda sedan 6 element (och gå tillbaka till bo gobogosorting 2).
• @pmg Om det är rätt definition av bogobogosort visar det sig att vara snabbare än bogosort (som OP ' s program visar) . Jag ' är inte bekant med bogobogosorts ursprung men för att den ska " springa tills universumets värmedöd " som påstått, det ska se mer ut som den typ jag skrev.