1.5. Néhány nem-hagyományos elvű algoritmus

Azért, hogy elszakadjunk a hagyományos értelemben vett „algoritmikus” gondolkodásmódtól mutatunk néhány olyan rendezési algoritmust, ami alapjában véve tér el a tanult rendezési módszerektől (beszúrásos-, buborékos-, legkisebb kiválasztásos-, gyorsrendezés, stb.).

1.5.1. A Spagetti-számítógép rendezési algoritmusa

Legyenek adva különböző hosszúságú rudak („spagettik”). A feladat az, hogy rendezzük őket hosszuk szerint sorrendbe. Ahelyett, hogy mindig egy-egy elemet hasonlítanánk össze egy másikkal (mint a hagyományos rendezési algoritmusoknál), az összeset egy kötegnek tekintjük: kézbe vesszük, és az asztalra állítjuk őket. (Lásd az 1.4. ábrát.)

1.4. ábra - A spagetti rendezés: egy csoportos összehasonlítással kiválasztható a leghosszabb elem.

A spagetti rendezés: egy csoportos összehasonlítással kiválasztható a leghosszabb elem.

Így ránézésre (egy méréssel) ki tudjuk választani közülük a legnagyobbat. Ezt kiemeljük, s a maradékot újra egy kötegnek tekintjük. Így elem esetén a rendezést lépésben, azaz lineáris időben hajthatjuk végre szemben a hagyományos algoritmusok általában négyzetes időbonyolultságával.

1.5.2. Rendezés a gravitáció segítségével

Most egy újabb rendezési algoritmust mutatunk be, ami egy mindennapi fizikai jelenségen, a gravitáción alapul.

Legyenek most adva a(z egész) számok, mint különböző hosszúságú kockacukor csíkok. A feladat az, hogy mondjuk meg a csíkok hosszait pl. csökkenő sorrendben. A rendezés során a gravitációt használjuk fel. Tegyük a csíkokat egymás fölé közös baloldali kezdőponttal. Ha az alakzatokat elengedjük, a nagyobb számokat jelentő csíkok kockacukrai behullanak a rövidebb csíkoknál levő lyukakba. Így a rendezés végére egy piramisszerű alakzatunk lesz, benne minden olyan szám szerepel (és ugyanannyiszor), mint az eredetiben. (Lásd pl. az 1.5. ábrán.)

1.5. ábra - A „gravitációs” rendezés.

A „gravitációs” rendezés.