Bogosort vs bogobogosort [uzavřeno]

Ne bogobogosort

Způsob, jakým jste svůj bogobogosort implementovali, je ve skutečnosti rychlejší než bogosort z několika důvodů:

1. Po úspěšném vytvoření k prvků okamžitě zkontrolujete, zda k+1 prvky jsou seřazeny. To znamená, že pokud jste při předchozím zamíchání náhodně zamíchali m prvky v pořadí, pak po seřazení prvních dvou prvků okamžitě dosáhnete m.

   Předpokládejme například, že dosáhnete 5 karet a poté selžete. Zaměníte 5 karet a poté začnete znovu na 2. Pokud je těch 5 karet v seřazeném pořadí, ihned dosáhnete 6, jakmile dáte první 2 karty do pořadí.

2. Kvůli bodu č. 1 je váš bogobogosort ve skutečnosti rychlejší než bogosort, protože místo n potřebuje pouze třídit n-1 karty. . Poté, co seřadí n-1 karty, zkontroluje pořadí n karet a může selhat. Pokud ale selže, provede přeskupení n karet tak, aby pokaždé, když seřadí n-1 karty, měl 1/n šance na úspěch. Celkový počet zamíchaných karet je tedy v řádu (n-1) * (n-1)! * n, což zjednodušuje (n-1) * n! ve srovnání s bogosortem, který zamíchá n * n! karty.

   Domnívám se, že v každém kroku platí stejný princip, takže čas je ještě menší než (n-1) * n!. Nejsem si jistý přesnou matematikou, ale po spuštění vašeho programu se zdá, že bogobogosort běží přibližně ve stejnou dobu jako bogosort s jednou kartou méně. Tj. Your_bogobogosort (n) = bogosort (n-1).

Řádný bogobogosort

Přepsal jsem vaši funkci bogobogosort tak, aby vypadala takto:

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

Klíčový rozdíl zde spočívá v tom, že po každém úspěchu, kde zvyšuje b, přeskupuje balíček, aby se zabránilo bodu č. 1 výše. S touto změnou dostanu výstup takto:

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

Komentáře

• Podle popisu na Wikipedii první část bogosortu kontroluje objednané data. Pokud jsou první N prvky v pořádku, bogosort těchto N prvků neprovede jediné zamíchání. Takže pokud mám 0 1 2 3 4 6 5 a bogobogosort, přejdu z bogosortu ze 2 na 5 prvky bez promíchání, poté zamíchejte 6 prvků (a vraťte se k bo gobogosorting 2).
• @pmg Pokud je to správná definice bogobogosortu, ukáže se, že je rychlejší než bogosort (jak dokazuje program OP ' s) . ' nejsem obeznámen s původem bogobogosortu, ale abych mohl " běžet až do smrtelné smrti vesmíru " jak se tvrdí, mělo by to vypadat spíše jako druh, který jsem napsal.