Библиотечко сортирање
From Wikipedia, the free encyclopedia
Библиотечко сортирање је алгоритам сортирања базиран на сортирању уметањем, који користи размаке унутар низа како би убрзао узастопна уметања. Овај алгоритам се још назива и сортирање уметањем са размаком, а библиотечким сортирањем се назива због следеће аналогије: Претпоставимо да библиотекар ређа књиге по азбучном реду на дугачкој полици, почевши од А-ова на левом крају и настављајући надесно дуж полице без размака између књига све до краја Ш-ова. Ако библиотекар добије нову књигу која припада Б секцији, када јој пронађе одговарајуће место, мораће да премести све књиге од тог места унутар Б-ова па све до последњег Ш-а, како би направио место за нову књигу. Ово је сортирање уметањем. Међутим, ако би оставио размак после сваког слова, докле год има места после Б-а, он ће морати да премести само пар књига на Б да би направио места за нову. Ово је основни принцип библиотечког сортирања.
Алгоритам су предложили Мајкл А. Бендер, Мартин Фарак-Колтон и Мигел Мостеиро 2004. године, а објавили 2006.
Као и сортирање уметањем на ком је базиран, овај алгоритам је један стабилан алгоритам сортирања поређењем. Показало се да постоји велика вероватноћа да временска сложеност буде О(nlogn), што је блиско квиксорту, за разлику од сортирања уметањем које има О(n^2) временску сложеност. Механизам који је коришћен је веома сличан механизму пропуштајуће листе. Нема потпуне имплементације у раду, нити тачно одређених алгоритама битних делова, као што су уметање и ребалансирање. Даље информације би биле неопходне за поређење ефикасности библиотечког сортирања са другим сортирањима у пракси.
У поређењу са основним сортирањем уметања, мана библиотечког сортирања је то што захтева додатни простор за размаке. Количина и распоред тог простора би зависили од имплементације. У раду се наводи да је потребна величина низа (1+ε)n, али без даљих назнака о томе како одабрати. Једна од слабости сортирања уметањем је то што би могло захтевати висок број операција замене и што би могло бити скупо у зависности од скупоће писања меморије. Библиотечко сортирање може побољшати ове ствари у кораку уметања, али и повећава цену у кораку ребалансирања.