Bogosort vs bogobogosort [lukket] (Norsk)

Ikke bogobogosort

Slik du implementerte bogobogosort, er det faktisk raskere enn bogosort becau av noen få grunner:

1. Etter at du har fullført k -elementer, sjekker du umiddelbart om k+1 elementene er sortert. Dette betyr at hvis du tilfeldigvis blandet m elementene i rekkefølge, så vil du umiddelbart nå m.

   Anta for eksempel at du når fem kort og deretter mislykkes. Du stokker 5 kort og begynner på nytt ved 2. Hvis disse 5 kortene tilfeldigvis er i sortert rekkefølge, når du umiddelbart 6 så snart du setter de to første kortene i orden.

2. På grunn av punkt 1 er bogobogosortet ditt faktisk raskere enn bogosortet fordi det bare trenger å sortere n-1 kort i stedet for n . Etter at den har sortert n-1 kort, sjekker den rekkefølgen på n kort og kan mislykkes. Men hvis det mislykkes, blandes det n kort slik at det hver gang det sorterer n-1 -kort, har et 1/n sjanse for til slutt å lykkes. Så det totale antallet kort som stokkes er i størrelsesorden (n-1) * (n-1)! * n som forenkler til (n-1) * n!, sammenlignet med bogosort som blander n * n! kort.

   Jeg mener at det samme prinsippet gjelder ved hvert trinn, så tiden er enda mindre enn (n-1) * n!. Jeg er ikke sikker på nøyaktig matematikk, men når du kjører programmet ditt, ser det ut til at bogobogosort kjører omtrent samme tid som bogosort med ett færre kort. Det vil si Your_bogobogosort (n) = bogosort (n-1).

En skikkelig bogobogosort

Jeg skrev om bogobogosort-funksjonen din slik:

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

Hovedforskjellen her er at etter hver suksess der den øker b, blandes den på nytt for å forhindre at punkt 1 ovenfor skjer. Med denne endringen får jeg utdata som dette:

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

Kommentarer

• I følge beskrivelsen på Wikipedia, sjekker den første delen av bogosort for bestilt data. Hvis de første N-elementene er i orden, gjør ikke en bogosort av disse N-elementene en eneste blanding. Så hvis jeg har 0 1 2 3 4 6 5 og bogobogosort at jeg går fra bogosort fra 2 til 5 elementer uten blanding, og bland deretter 6 elementer (og gå tilbake til bo gobogosorting 2).
• @pmg Hvis det er riktig definisjon av bogobogosort, viser det seg å være raskere enn bogosort (som OP ' s program viser) . Jeg ' er ikke kjent med opprinnelsen til bogobogosort, men for at den skal " løpe til varmedødet til universet " som påstått, det skal se mer ut som den typen jeg skrev.