Bead sort

Bead sort je algoritam za sortiranje, razvijen od strane Joshua J. Arulanandham, Cristian S. Calude i Michael J. Dinneen 2002-ge, i objavljen u biltenu The Bulletin of the European Association for Theoretical Computer Science. I digitalna i analogna hardverska implementacija bead sorta može da dostigne vreme O(n); ipak, softverska implementacija ovog algoritma može da bude znatno sporija i može se koristiti samo za sortiranje pozitivnih celih brojeva. Takođe, čini se da i u najboljem slučaju algoritam zahteva prostornu složenost O(n²).

Pregled algoritma

Korak 1: Viseće perle na vertikalnim štapovima.

Operacija bead sorta može da se poredi sa načinom na koji perle klize na paralelnim šipkama, slično kao na abakusu. Ipak, svaka šipka može imati različiti broj perli. Inicijalno, može biti od pomoći da zamislimo perle obešene na vertikalnim šipkama. U prvom koraku, takav raspored je prikazan koristeći n=5 redova perli i m=4 šipki. Brojevi sa desne strane svakog reda označavaju broj koji taj red predstavlja. Redovi 1 i 2 predstavljaju pozitivni ceo broj 3 (zato što svaki od njih sadrži 3 perle) dok gornji red predstavlja pozitivni ceo broj 2 (jer on sadrži samo 2 perle). Ako onda dozvolimo da perle padnu, redovi će predstavljati iste cele brojeve u sortiranom redu. Prvi red sadrži najveći broj u grupi, dok n-ti red sadrži najmanji. Ako je gorepomenuta konvencija redova koji sadrže nizove perli na šipkama 1..k i koja ostavlja šipke k+1..m prazne praćena, i ovde će biti takav slučaj.

Dopuštanje da perle padnu u našem konkretnom primeru je dozvolilo većim vrednostima iz viših redova da napreduju do nižih redova. Ako je vrednost koja je predstavljena redom a manja nego vrednost sadržana u redu a+1, neke od perli iz reda a+1 će pasti u red a; ovo će se sigurno desiti jer red a ne sadrži perle na onim pozicijama koje bi sprečile perle iz reda a+1 da padnu.

Mehanizam koji je u osnovi bead sorta je sličan onome u osnovi counting sort; broj perli na svakoj šipki odgovara broju elemenata vrednosti jednake ili veće od indeksa te šipke.

Složenost

Bead sort se može implementirati sa 3 opšta nivoa složenosti:

O(1): Sve perle se pomeraju istovremeno, u istom vremenskom intervalu, kao što bi bio slučaj sa jednostavnim gorepomenutim primerom. Ovo je apstraktna složenost i ne može se implementirati u praksi.
O( ${\sqrt {n}}$ ): U fizičkom modelu koji koristi gravitaciju, vreme potrebno da perle padnu je proporcionalno kvadratnom korenu maksimalne visine, koji je proporcionalan broju n.
O(n): Perle se pomeraju red-po-red. Ovo je slučaj koji se koristi u analognim i digitalnim hardverskim rešenjima.
O(S), gde je S suma celih brojeva sa ulaza: svaka perla se pomera pojedinačno. Ovo je slučaj kada se bead sort implementira bez mehanizma koji bi asistirao u pronalaženju praznih prostora ispod perli kao što je slučaj kod softverskih implementacija.

Kao kod Pigeonhole sort-a, bead sort je neobičan po tome što može da radi u vremenu bržem od O(nlogn), što je najbrže vreme kod algoritama poređenja. Ovo je moguće zato što je ključ za bead sort uvek pozitivan ceo broj i bead sort koristi njegovu strukturu.