Az egyetemi könyvtárban dolgozol.
Napod már a vége felé közeledik,
amikor hirtelen befut egy 1280 különböző könyvből álló szállítmány.
A könyveket egy vonalban, egymás mellé rakják le,
de rendezetlen az egész,
és az automatikus osztályozó rendszer elromlott.
Ha ez még nem lenne elég, holnap tanítási nap,
így az első dolog reggel az lesz,
hogy tanulók tömegei fogják ezeket a könyveket keresni.
Hogyan tudod őket időben elrendezni?
Kezdhetnénk úgy, hogy az egyik végéről felveszed az első két könyvet.
Ha azok sorrendben vannak, hagyd úgy, ahogy voltak.
Máskülönben felcseréljük őket.
Majd jön a második, harmadik pár,
a folyamat ismétlődik.
Ezt egészen addig folytatod, amíg a sor végére érsz.
Lesz, hogy az utolsónak szánt könyv kerül a kezedbe,
és addig teszed a mögötte lévő könyvek után,
amíg oda nem érsz, ahová az tartozik, a végére.
Majd a folyamat újraindul, kezded elölről,
hogy az utolsó előtti könyv is helyére kerüljön,
ez addig megy, míg mindegyik rendben lesz.
Ezt a módszert buborékrendezésnek hívjuk.
Egyszerű, viszont lassú.
Első körben 1279-szer veted őket össze,
majd 1278-szer és így tovább,
összesen 818 560-szor csinálod meg.
Ha másodpercenként egyet vetnél össze, a folyamat kilenc napig tartana.
A másik módszer az lehetne, hogy az első két könyvvel kezdenél.
Majd hozzávennéd a harmadikat, és összevetnéd a második helyen lévővel.
Ha azt a második hely illeti meg, megcseréled őket,
majd az első helyen lévővel veted össze,
és ha kell, megint megcseréled.
Eddig sorba raktad az első három könyvet.
Adj hozzá mindig egy könyvet a már rendezettekhez,
vesd össze és cseréld meg az új könyvet az előtt lévővel,
amíg a sorba rakott könyvek között helyére nem kerül.
Ezt beszúrásos rendezésnek hívjuk.
A buborékrendezéssel ellentétben itt nem kell minden könyvet összevetni.
Arra számíthatunk, hogy átlagosan egy-egy könyvet
csak az előttük lévők felével kell összevetni.
Ebben az esetben az összevetések száma
409 280 lenne,
majdnem öt napig tartana.
Még mindig túl sokszor veted őket össze.
Íme, egy jobb ötlet:
Véletlenszerűen kiveszel egy könyvet.
Nevezd el válaszelemnek, és vessük össze mindegyik könyvvel.
Majd válaszd szét a sort úgy,
hogy a válaszelem előtti könyvek bal oldalra,
az utána következők pedig jobb oldalra mennek.
Rengeteg időt spóroltál,
hogy többet nem veted össze a baloldali könyveket
a jobboldaliakkal.
Most csak a baloldaliakat nézve,
újabb válaszelemet vehetsz ki,
és elkülönítheted az előtte és az utána jövő könyveket.
Addig osztasz további kisebb válaszelemekre,
amíg sok-sok kis válaszfal nem lesz,
melyek között más módszerrel, pl. beszúrásos rendezéssel rendet teszünk.
Egy-egy elválasztáshoz 1280 összevetés kell.
Ha válaszelemeid egyenlő távolságra rakod,
ha minden tizedik könyvhöz teszünk egy válaszfalat, ami 128 darab,
úgy hét kör kell vagy 8960 másodperc.
A válaszfalak közötti rendezés egyenként 22 másodpercet venne igénybe.
Ezzel az ún. gyorsrendezéssel egészében véve
három órán belül sorba lehet rakni a könyveket.
De van hátulütője.
A válaszelemek aránytalanságával nem spórolnál semmit.
Szerencsére ez ritkán történik.
Ezért van, hogy a gyorsrendezés ma az egyik leghatékonyabb,
programozók által használt módszer.
Például ezzel rakják sorba ár szerint online boltok készletét,
vagy benzinkutakat listáznak ki egy adott helytől
távolság szerint.
Esetedben a rendezés után maradt még időd.
Csak egy újabb rázós nap a könyvtárban.