Беад сорт

Беад сорт је алгоритам за сортирање, развијен од стране Јосхуа Ј. Аруланандхам, Цристиан С. Цалуде и Мицхаел Ј. Диннеен 2002-ге, и објављен у билтену Тхе Буллетин оф тхе Еуропеан Ассоциатион фор Тхеоретицал Цомпутер Сциенце. I дигитална и аналогна хардверска имплементација беад сорта може да достигне време О(н); ипак, софтверска имплементација овог алгоритма може да буде знатно спорија и може се користити само за сортирање позитивних целих бројева. Такође, чини се да и у најбољем случају алгоритам захтева просторну сложеност О(н²).

Преглед алгоритма

Корак 1: Висеће перле на вертикалним штаповима.

Корак 2: Перлама је омогућено да падну.

Операција беад сорта може да се пореди са начином на који перле клизе на паралелним шипкама, слично као на абакусу. Ипак, свака шипка може имати различити број перли. Иницијално, може бити од помоћи да замислимо перле обешене на вертикалним шипкама. У првом кораку, такав распоред је приказан користећи н=5 редова перли и м=4 шипки. Бројеви са десне стране сваког реда означавају број који тај ред представља. Редови 1 и 2 представљају позитивни цео број 3 (зато што сваки од њих садржи 3 перле) док горњи ред представља позитивни цео број 2 (јер он садржи само 2 перле). Ако онда дозволимо да перле падну, редови ће представљати исте целе бројеве у сортираном реду. Први ред садржи највећи број у групи, док н-ти ред садржи најмањи. Ако је горепоменута конвенција редова који садрже низове перли на шипкама 1..к и која оставља шипке к+1..м празне праћена, и овде ће бити такав случај.

Допуштање да перле падну у нашем конкретном примеру је дозволило већим вредностима из виших редова да напредују до нижих редова. Ако је вредност која је представљена редом а мања него вредност садржана у реду а+1, неке од перли из реда а+1 ће пасти у ред а; ово ће се сигурно десити јер ред а не садржи перле на оним позицијама које би спречиле перле из реда а+1 да падну.

Механизам који је у основи беад сорта је сличан ономе у основи цоунтинг сорт; број перли на свакој шипки одговара броју елемената вредности једнаке или веће од индекса те шипке.

Сложеност

Беад сорт се може имплементирати са 3 општа нивоа сложености:

• О(1): Све перле се померају истовремено, у истом временском интервалу, као што би био случај са једноставним горепоменутим примером. Ово је апстрактна сложеност и не може се имплементирати у пракси.
• О(${\sqrt {n}}$): У физичком моделу који користи гравитацију, време потребно да перле падну је пропорционално квадратном корену максималне висине, који је пропорционалан броју н.
• О(н): Перле се померају ред-по-ред. Ово је случај који се користи у аналогним и дигиталним хардверским решењима.
• О(С), где је С сума целих бројева са улаза: свака перла се помера појединачно. Ово је случај када се беад сорт имплементира без механизма који би асистирао у проналажењу празних простора испод перли као што је случај код софтверских имплементација.

Као код Пигеонхоле сорт-а, беад сорт је необичан по томе што може да ради у времену бржем од О(нлогн), што је најбрже време код алгоритама поређења. Ово је могуће зато што је кључ за беад сорт увек позитиван цео број и беад сорт користи његову структуру.

Спољашње везе

• Тхе Беад Сорт папер Архивирано на сајту Wayback Machine (9. август 2017)
• Беад Сорт ин МГС, а висуализатион оф а беад сорт имплементед ин тхе МГС программинг лангуаге
• Беад Сорт он МатхWорлд