Bogosort vs bogobogosort [lukket]

Ikke bogobogosort

Den måde, du implementerede din bogobogosort på, det er faktisk hurtigere end bogosort becau af nogle få grunde:

1. Når du har bogosorteret k -elementer, kontrollerer du straks, om k+1 elementer sorteres. Dette betyder, at hvis du ved en tidligere blanding tilfældigvis blandede m elementer i orden, så når du sorterer de to første elementer, når du straks m.

   Antag for eksempel, at du når 5 kort og derefter fejler. Du blander 5 kort og starter derefter igen ved 2. Hvis disse 5 kort tilfældigvis er i sorteret rækkefølge, når du straks 6, så snart du sætter de første 2 kort i orden.

2. På grund af punkt 1 er din bogobogosort faktisk hurtigere end bogosorten, fordi den kun behøver at sortere n-1 kort i stedet for n . Når det har sorteret n-1 kort, kontrollerer det rækkefølgen af n kort og kan mislykkes. Men hvis det fejler, skifter det n kort, så det hver gang det sorterer n-1 -kort, det har et 1/n chance for til sidst at lykkes. Så det samlede antal kort, der blandes, er i størrelsesordenen (n-1) * (n-1)! * n, hvilket forenkles til (n-1) * n! sammenlignet med bogosortet, der blandes n * n! -kort.

   Jeg mener, at det samme princip gælder for hvert trin, så tiden er endnu mindre end (n-1) * n!. Jeg er ikke sikker på den nøjagtige matematik, men når du kører dit program, ser det ud til, at bogobogosort kører omtrent samme tid som bogosort med et færre kort. Det vil sige Your_bogobogosort (n) = bogosort (n-1).

En ordentlig bogobogosort

Jeg omskrev din bogobogosort-funktion til at være sådan:

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

Nøgleforskellen her er, at efter hver succes, hvor den forøger b, skifter det dækket om for at forhindre, at punkt 1 ovenfor sker. Med denne ændring får jeg output som dette:

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

Kommentarer

• Ifølge beskrivelsen på Wikipedia kontrollerer bogosort første del for bestilt data. Hvis de første N-elementer er i orden, foretager en bogosort af disse N-elementer ikke en enkelt blanding. Så hvis jeg har 0 1 2 3 4 6 5 og bogobogosort, går jeg fra bogosort fra 2 til 5 elementer uden blanding, bland derefter 6 elementer (og gå tilbage til bo gobogosorting 2).
• @pmg Hvis det er den korrekte definition af bogobogosort, viser det sig at være hurtigere end bogosort (som OP ' s program viser) . Jeg ' er ikke bekendt med bogobogosorts oprindelse, men for at den skal " løber indtil universets varmedød " som hævdet, det skal ligne mere på den slags, jeg skrev.