Bogosort vs bogobogosort [bezárt]

Nem bogobogosort

Ahogy a bogobogosort megvalósította, valójában gyorsabb, mint a bogosort becau néhány okból következik:

1. Miután sikeresen elrendezte az k elemeket, azonnal ellenőrizze, hogy k+1 elemek rendezve vannak. Ez azt jelenti, hogy ha egy korábbi keverés során véletlenül sorrendbe keverte az m elemeket, akkor az első két elem rendezése után azonnal elérheti az m.

   Tegyük fel például, hogy elérte az 5 kártyát, majd kudarcot vall. Összekevered 5 kártyát, majd a 2. pontnál kezded elölről. Ha ez az 5 kártya véletlenszerűen rendezett sorrendben van, akkor azonnal eléred a 6-ot, amint az első 2 kártyát rendbe teszed.

2. Az 1. pont miatt a bogobogosortod gyorsabb, mint a bogosort, mert csak n-1 kártyákat kell rendezni n helyett . Miután rendezi a n-1 kártyákat, ellenőrzi az n kártyák sorrendjét, és meghibásodhat. De ha nem sikerül, akkor átalakítja a n kártyákat úgy, hogy minden egyes alkalommal, amikor n-1 kártyákat válogat, 1/n esély a sikerre. Tehát az összes megkevert kártya száma (n-1) * (n-1)! * n nagyságrendű, ami (n-1) * n! -re egyszerűsödik, összehasonlítva a bogosorttal, amely keveri a n * n! kártyák.

   Úgy gondolom, hogy minden lépésnél ugyanaz az elv érvényesül, ezért az idő még kevesebb, mint a (n-1) * n!. Nem vagyok biztos a pontos matematikában, de a program futtatásából úgy tűnik, hogy a bogobogosort körülbelül ugyanabban az időben fut, mint a bogosort, egynél kevesebb kártyával. Vagyis a_bogobogosort (n) = bogosort (n-1).

Megfelelő bogobogosort

Átírtam a bogobogosort funkciót, hogy ilyen legyen:

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

A legfontosabb különbség itt az, hogy minden olyan siker után, ahol növekszik a b, átalakítja a fedélzetet, hogy megakadályozza a fenti 1. pont bekövetkezését. Ezzel a változtatással a következő kimenetet kapom:

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

Megjegyzések

• A Wikipedia leírásának megfelelően a bogosort első része ellenőrzi a megrendeléseket adatok. Ha az első N elem rendben van, akkor az N elem bogosortja nem végez egyetlen keverést. Tehát ha van 0 1 2 3 4 6 5 és bogobogosortom, akkor a bogosortról 2-ről 5-re megyek elemek keverése nélkül, majd keverje össze 6 elemet (és menjen vissza a bo gobogosorting 2).
• @pmg Ha ez a bogobogosort helyes meghatározása, akkor gyorsabbnak bizonyul, mint a bogosort (amint azt az OP ' s program bizonyítja) . Én ' nem ismerem a bogobogosort eredetét, de ahhoz, hogy " az univerzum hőhaláláig fuss " amint azt állítottuk, inkább annak kell kinéznie, amilyet írtam.