Š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).

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

Spoljašnje veze 
 -{A. K. Dewdney's homepage}-
 -{Classical/Quantum Computing, IFF-Institute}-

Алгоритми сортирања
Š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 ) . 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 Spoljašnje veze -{ A . K . Dewdney's homepage }- -{ Classical / Quantum Computing , IFF-Institute }- Алгоритми сортирања