Špagetno sortiranje

Špagetno sortiranje je analogni algoritam sa linearnom vremenskom složenošcu, koji sortira niz predmeta. Prvi ga je predstavio Alexander Dewdney u svojoj kolumni za magazin Scientific American (ili kraće SciAm).^[1]^[2]^[3]

Algoritam

Radi jednostavnosti, pretpostavimo da sortiramo listu prirodnih brojeva. Metod sortiranja je prikazan tako da koristi nekuvane štapiće špageta:

Za svaki broj x iz liste, dobijamo štapić dužine x. (Praktičan način za odabir jedinice je da pustimo da najveći broj m u listi odgovara jednom celom štapiću špageta. U ovom slučaju ceo štapić je jednak m jedinica špageta. Da bi dobili štapić dužine x, jednostavno podelimo štapić na dva dela kako bi jedan deo bio dužine x jedinica; drugi deo uklonimo.)
Jednom kad dobijemo sve štapiće špageta, stavimo ih labavo u šaku i spustimo ih na sto, tako da svi štapići stoje uspravno, oslanjajući se na površinu stola. Sada spuštamo ruku ka štapićima, dok ne dodirnemo jedan. Onaj koga prvo dodirnemo je naravno najduži. Uklonimo ovaj štapić, i stavimo ga u prednjem delu izlazne liste (koja je inicijalno prazna), (ili ekvivalentno, smestimo ga na zadnjem neiskorišćenom mestu u izlaznom nizu.). Ovaj postupak ponavljamo sve dok imamo štapiće koje treba ukloniti.

Analiza

Priprema n štapića špageta oduzima linearno vreme. Spuštanje štapića na sto ima konstantno vreme, O(1). Ovo je moguće zbog ruke, dok štapici špageta i sto funkcionišu kao uređaj koji paralelno računa. Ako imamo n štapića koje je potrebno ukloniti, pretpostavljajući da svaka operacija dodirivanja i uklanjanja zahteva konstantno vreme, složenost najgoreg slučaja je O(n).

Prostorna složenost je isto minimalna: O(n), izmereno štapićima špageta.

Reference

^ Dewdney, A. K. (jun 1984), „On the spaghetti computer and other analog gadgets for problem solving”, Scientific American, 250 (6), стр. 19—26
^ Stauffer, Dietrich (15. 5. 1999), Annual Reviews of Computational Physics VI, World Scientific, стр. 260, ISBN 978-981-02-3563-5
^ Adamatzky, Andrew (1. 7. 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, стр. 96, ISBN 978-0-9551170-9-1

Spoljašnje veze

[1] Dewdney, A. K. (jun 1984), „On the spaghetti computer and other analog gadgets for problem solving”, Scientific American, 250 (6), стр. 19—26

[2] Stauffer, Dietrich (15. 5. 1999), Annual Reviews of Computational Physics VI, World Scientific, стр. 260, ISBN 978-981-02-3563-5

[3] Adamatzky, Andrew (1. 7. 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, стр. 96, ISBN 978-0-9551170-9-1

[1]

[2]

[3]