Nu bogobogosort
Modul în care v-ați implementat bogobogosort, este de fapt mai rapid decât bogosort becau câteva motive:
-
După ce ați bogosort cu succes k elemente, verificați imediat dacă k+1 elementele sunt sortate. Aceasta înseamnă că, dacă într-un amestec anterior, vi s-a întâmplat să amestecați m elementele toate în ordine, atunci după ce sortați primele două elemente, veți ajunge imediat la m.
De exemplu, să presupunem că atingi 5 cărți și apoi eșuezi. Amestecați 5 cărți și apoi începeți de la 2. Dacă aceste 5 cărți se întâmplă să fie în ordine sortată, veți ajunge imediat la 6 imediat ce puneți primele 2 cărți în ordine.
-
Din cauza punctului # 1, bogobogosortul dvs. este de fapt mai rapid decât bogosortul, deoarece trebuie doar să sorteze cardurile n-1 în loc de n . După ce sortează cardurile n-1, verifică ordinea cardurilor n și poate eșua. Dar, în caz de eșec, remodelează n cărțile astfel încât de fiecare dată când sortează n-1 cărțile să aibă un 1/n șansa de a reuși în cele din urmă. Deci, numărul total de cărți amestecate este de ordinea (n-1) * (n-1)! * n, care se simplifică la (n-1) * n!, comparativ cu bogosortul care amestecă .
Cred că același principiu se aplică la fiecare pas, deci timpul este chiar mai mic decât (n-1) * n!. Nu sunt sigur de matematica exactă, dar din rularea programului dvs. se pare că bogobogosort rulează aproximativ în același timp cu bogosort cu încă câteva cărți. Adică Your_bogobogosort (n) = bogosort (n-1).
Un bogobogosort adecvat
Am rescris funcția bogobogosort astfel încât să fie astfel:
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; }
Diferența esențială aici este că, după fiecare succes în care crește b, remodelează pachetul pentru a împiedica punctul # 1 de mai sus să se întâmple .. Cu această modificare, obțin rezultate astfel:
% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds.
Comentarii