Bogosort vs bogobogosort [closed]

Non bogobogosort

Il modo in cui hai implementato il tuo bogobogosort, in realtà è più veloce di bogosort perché per alcuni motivi:

1. Dopo aver bogosortato con successo gli elementi k, controlli immediatamente se k+1 gli elementi vengono ordinati. Ciò significa che se in una precedente riproduzione casuale ti è capitato di mescolare m elementi tutti in ordine, dopo aver ordinato i primi due elementi, raggiungerai immediatamente m.

   Ad esempio, supponi di raggiungere 5 carte e poi fallisci. Mescoli 5 carte e poi ricomincia da 2. Se queste 5 carte sono in ordine, raggiungerai immediatamente 6 non appena metti in ordine le prime 2 carte.

2. A causa del punto n. 1, il tuo bogobogosort è effettivamente più veloce del bogosort perché deve solo ordinare le n-1 carte invece di n . Dopo aver ordinato le n-1 schede, controlla lordine delle n schede e potrebbe non riuscire. Tuttavia, se fallisce, rimescola le n schede in modo che ogni volta che ordina le n-1 schede abbia un 1/n possibilità di successo. Quindi il numero totale di carte mescolate è nellordine di (n-1) * (n-1)! * n che si semplifica in (n-1) * n!, rispetto al bogosort che mescola n * n! card.

   Credo che lo stesso principio si applichi a ogni passaggio, quindi il tempo è anche inferiore a (n-1) * n!. Non sono sicuro della matematica esatta, ma dallesecuzione del programma sembra che bogobogosort venga eseguito allincirca nello stesso tempo di bogosort con una carta in meno. Ad esempio Your_bogobogosort (n) = bogosort (n-1).

Un bogobogosort appropriato

Ho riscritto la tua funzione bogobogosort in questo modo:

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

La differenza fondamentale qui è che dopo ogni successo in cui aumenta b, rimescola il mazzo per evitare che il punto n. 1 sopra accada .. Con questa modifica, ottengo un output come questo:

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

Commenti

• Secondo la descrizione su Wikipedia, la prima parte di bogosort sta controllando per ordinato dati. Se i primi N elementi sono in ordine, un bogosort di quegli N elementi non fa un singolo shuffle. Quindi se ho 0 1 2 3 4 6 5 e bogobogosort che vado da bogosort da 2 a 5 elementi senza mescolare, quindi mescolare 6 elementi (e tornare a bo gobogosorting 2).
• @pmg Se questa è la definizione corretta di bogobogosort, allora risulta essere più veloce di bogosort (come dimostra il programma OP ') . ' non conosco le origini di bogobogosort, ma affinché " corra fino alla morte termica delluniverso " come affermato, dovrebbe assomigliare di più al tipo che ho scritto.