Bogosort vs bogobogosort [suljettu]

ei bogobogosort

Tapa, jolla toteutit bogobogosortisi, on itse asiassa nopeampi kuin bogosort becau muutamista syistä:

1. Kun olet onnistuneesti bogosort k -elementit, tarkistat heti, onko k+1 -elementit lajitellaan. Tämä tarkoittaa, että jos edellisessä sekoituksessa sattuit sekoittamaan m -elementtejä kaikki järjestyksessä, sitten kun lajittelet kaksi ensimmäistä elementtiä, pääset heti m.

   Oletetaan esimerkiksi, että saavutat 5 korttia ja epäonnistut sitten. Sekoitat 5 korttia ja aloitat sitten alusta kohdasta 2. Jos nämä 5 korttia sattuu olemaan lajiteltu järjestyksessä, saavut heti kuusi heti, kun laitat kaksi ensimmäistä korttia järjestykseen.

2. Pisteen 1 takia bogobogosort on todella nopeampi kuin bogosort, koska sen täytyy vain lajitella n-1 -kortit n . Kun se lajittelee n-1 kortit, se tarkistaa n -korttien järjestyksen ja saattaa epäonnistua. Mutta epäonnistumisessa se muuttaa n -kortteja siten, että joka kerta kun lajittelee n-1 kortit, sillä on 1/n mahdollisuus menestyä. Joten sekoitettujen korttien kokonaismäärä on luokkaa (n-1) * (n-1)! * n, mikä yksinkertaistuu muotoon (n-1) * n! verrattuna bogosorttiin, joka sekoittaa n * n! -kortit.

   Uskon, että sama periaate pätee kussakin vaiheessa, joten aika on jopa pienempi kuin (n-1) * n!. En ole varma tarkasta matematiikasta, mutta ohjelman suorittamisesta näyttää siltä, että bogobogosort toimii suunnilleen samaan aikaan kuin bogosort yhdellä kortilla vähemmän. Eli Sinun_bogobogosort (n) = bogosort (n-1).

Oikea bogobogosort

Kirjoitin bogobogosort-toimintosi uudestaan seuraavasti:

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

Tärkein ero tässä on se, että jokaisen menestyksen jälkeen, jossa se kasvaa b, se muuttaa kannen uudelleen estääkseen yllä olevan piste 1: n. Tämän muutoksen myötä saan seuraavanlaisen tuloksen:

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

Kommentit

• Wikipedian kuvauksen mukaan bogosortin ensimmäinen osa tarkistaa tilauksen data. Jos ensimmäiset N elementtiä ovat järjestyksessä, näiden N elementtien bogosortti ei tee yhtä sekoitusta. Joten jos minulla on 0 1 2 3 4 6 5 ja bogobogosort, siirryn bogosortista 2-5 elementtejä ilman sekoittamista, sekoita sitten 6 elementtiä (ja palaa takaisin bo gobogosorting 2).
• @pmg Jos tämä on oikea bogobogosort-määritelmä, se osoittautuu nopeammaksi kuin bogosort (kuten OP ' s -ohjelma todistaa) . En ' ole perehtynyt bogobogosortin alkuperään, mutta jotta se " toimisi universumin lämpökuolemaan asti " väitetysti sen pitäisi näyttää enemmän kuin kirjoittamani.