Bogosort vs bogobogosort [bezárt]

Zárt. Ez a kérdés témán kívüli . Jelenleg nem fogadja el a válaszokat.

Megjegyzések

  • Számomra ez dobja fel sorties.c: In function ‘timedelta’: sorties.c:82:18: error: dereferencing pointer to incomplete type double aa = a->tv_sec + (a->tv_nsec / 1000000000.0); ^ sorties.c:82:31: error: dereferencing pointer to incomplete type double aa = a->tv_sec + (a->tv_nsec / 1000000000.0); ^ sorties.c:83:18: error: dereferencing pointer to incomplete type double bb = b->tv_sec + (b->tv_nsec / 1000000000.0); ^ ... az GCC melyik verzióját futtassam?
  • I ' m a FreeBSD-n, a 3.4.1. De eltávolíthatja az időzítési kódot a program teljesen normál változatához.
  • Én ' szavazom, hogy a kérdést témakörön kívül zárjam, mert bármilyen ésszerű definíció " javítása " nem alkalmazható erre a kódra, amely csak a lehető legkisebb teljesítményt kívánja elérni.
  • I ' lezártam a kérdést, mert a kód nem ' nem működik rendeltetésszerűen (te ' újra megkérdezzük, miért nem működik a bogobogosort ' elég lassan).
  • Ott ' jobban leírható a bogobogosort algoritmus a dangermouse.net/esoteric/bogobogosort.html címen – ez nem valósítja meg az ott leírt algoritmust.

Válasz

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.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük