Адаптивно сортирање
Алгоритам за сортирање спада у групу адаптивног сортирања, ако користи постојећи поредак на улазу. Адаптивно сортирање се углавном врши изменом постојећих алгоритама за сортирање.
Мотивација[уреди | уреди извор]
Алгоритми који су засновани на поређењима су традиционално тежили остваривању временску сложеност O(n). Адаптивно сортирање има предност у томе сто већ постоји ред у улазу, тако да може да постигне и бољу сложеност. Према томе време за сортирање је функција која полако расте са повећањем низа и "нереда" у њему. Другим речима, што је низ више сортиран при уносу, то је алгоритам бржи.
Ово је занимљив алгоритам, јер се низови који су већ уређени често срећу у пракси. Учинак постојећих алгоритама за сортирање може бити доказан узимајући у обзир пресортираност низа.
Приметите да већина алгоритама који имају најбољу временску сложеност процењену на најгорем случају, посебно хипсорт и мергесорт, не узимају у обзир претходну уређеност улазног низа, иако је овај недостатак лако приметити, нарочито код мергесорт-а провером да ли је леви елемент мањи или једнак од првог десног. У том случају мергесорт може бити замењен једноставном конкатенацијом- модификацијом која је добра у случају прављења прилагодљивог сортирања.
Примери[уреди | уреди извор]
Класичан пример адаптивног сортирања је сортирање уметањем. У овом алгоритму пролазимо кроз низ с лева на десно и тражимо позицију за тренутни елемент и умећемо га у претходно сортирани низ. Псеудокод овог алгоритма изгледа овако:
procedure Straight Insertion Sort (X, n):
X[0] := − ∞;
for j := 2 to n do
begin i := j − 1;
t := X[j];
while t < X[i] do
begin X[i + 1] := X[i];
i := i - 1
end;
X[i + 1] := t;
end;
Перформансе овог алгоритма могу бити описане бројем инверзија улаза. Онда ће Т(н) бити I(А)+ (н-1), где је I(А) број инверзија. Користећи ове мере преуређености-које су у вези са бројем инверзија-сортирање уметањем брже сортира уређени низ. Други примери адаптивног сортирања су прилагодљиво хип сортирање и адаптивно сортирање спајањем. Дијкстрин Смутсорт је такође варијација хипсорта која подразумева коришћење алгоритма адапривног сортирања.
Тимсорт који се користи као генетички алгоритам за сортирање за више програмских језика, нпр. Пајтон, такође је адаптивни.
Литература[уреди | уреди извор]
- Хагеруп, Торбен; Катјаинен, Јyрки (2004). Алгоритхм Тхеорy – СWАТ 2004. Берлин Хеиделберг: Спрингер-Верлаг. стр. 221—222. ИСБН 978-3-540-22339-9.
- Мехта, Динесх П.; Сахни, Сартај (2005). Дата Струцтурес анд Апплицатионс. УСА: Цхапман & Халл/ЦРЦ. стр. 11‑8—11‑9. ИСБН 978-1-58488-435-4.
- Естивилл-Цастро, Владмир; Дерицк Wоод (1992). „А сурвеy оф адаптиве сортинг алгоритхмс”. АЦМ. Неw Yорк, НY, УСА: АЦМ. 24 (4): 441—476. ИССН 0360-0300. дои:10.1145/146370.146381.
- Петерссон, Ола; Алистаир Моффат (1992). „А фрамеwорк фор адаптиве сортинг”. Лецтуре Нотес ин Цомпутер Сциенце. Берлин: Спрингер Берлин / Хеиделберг. 621: 422—433. ИССН 1611-3349. дои:10.1007/3-540-55706-7_38. Приступљено 23. 02. 2009.[мртва веза]