Блоксорт, је алгоритам сортирања који спада у групу стабилних алгоритама сортирања, и састоји се од најмање две операције спајања и од сортирања уметањем у О(nlogn) времену у месту. Назив је добио из закључка да спајање две сортиране листе, А и Б, је еквивалентно дељењу А у блокове једнаких величина, и убацивање сваког блока А у листу Б под специјалним условима, и спајање АБ пара.
Један практичан алгоритам за блоксорт су предложили Pok-Son Kim и Arne Kutzner 2008. године.
Преглед Спољашња петља блоксорта је идентична алгоритму сортирања спајањем са имплементацијом одоздо-нагоре, где сваки ниво сортирања спаја парове поднизова, А и Б, у величинама од 1, затим 2, па 4, 8, 16, и тако даље, све док оба подниза не буду постали један низ.
Уместо спајања А и Б традиционалном методом, алгоритам спајања са блоковима дели А у одвојене блокове величина (што даје блокова), убацује се сваки блок А у Б тако да прва вредноста сваког блока А буде мања или једнака од вредности Б, локално спаја сваки блок А са било којом вредношћу између Б блока и следећег А блока. Пошто спајање и даље захтева довољно велики бафер да може да прихвати блок А који се спаја, два дела у низу су резервисана за ову сврху (познатији као интерни тј унутрашњи бафери). Прва два А блока су зато модификована да садрже прву инстанцу сваке вредности из А, са правим садржајем ових блокова који се померају (шифтују) ако је неопходно. Преостали А блок се онда умеће у Б и спаја се помућу једног од два бафера који служе као простор замене. Због овог процеса, вредност у том баферу се мора преуредити.
Једном кад се сваки А и Б блок сваког А и Б подниза споје за тај ниво сортирања спајањем, онда се вредности у том баферу могу сортирати да би повратили своје првобитно уредјење (поредак), па се сортирање уметањем мора искористити. Вредности у баферима се расподељују према њиховим првим сортираним позицијама у низу. Овај процес се понавља за сваки ниво сортирања спајањем (спољашња одоздо нагоре имплементација), и у том тренутку низ ће бити стабилно сортиран.
Алгоритам Следећи оператори се користе у примеру кода: | инклузивно или >> шифтовање удесно % модуло ++ i += инкремент [x, y) распон od ≥ x и < y |распон| распон.крај - распон.почетак niz[i] елемент низа
Такође, блоксорт користи следеће операције као део алгоритма: Замена: мења позиције две вредности у низу. Блок замена: мења распон вредности у низу са вредностима у другом распону низа. Бинарна претрага: претпостављамо да је низ сортиран, проверава средњу вредност тренутног опсега, затим ако је вредност мања проверава доњи распон, а ако је већа проверава горњи распон. Блоксорт користи две варијанте: једна која проналази прву позицију за убацивање у сортирани низ, и другу варијанту која проналази последњу позицију. Линеарна претрага: тражи одређену вредност у низу проверавајући сваки елемент у поретку, све док га не нађе. Сортирање уметањем: за сваки елемент у низу, пролази кроз петљу од позади и тражи где треба да се убаци елемент, а затим га и стави на ту позицију. Ротирање низа: померање елемената низа улево или десно неким бројем размака, вредностима са крајева низа. Ротацја може бити имплементирана као окретање стабла.
Rotiraj(niz, kolicina, raspon) Obrni(niz, raspon) Obrni(niz, [raspon.pocetak, raspon.pocetak + kolicina)) Obrni(niz, [raspon.pocetak + kolicina, raspon.kraj)) Највећи цео број степена 2: је селдећа вредност степена 2. 63 постаје 32, 64 остаје 64, итд.
CeoBrojStepenaDva(x) x = x | (x >> 1) x = x | (x >> 2) x = x | (x >> 4) x = x | (x >> 8) x = x | (x >> 16) if (ovo je 64-bitni sistem) x = x | (x >> 32) return x - (x >> 1) Спољашња петља Као што смо навели, спољашња петља Блоксорта је идентична као имплементација одоздо-нагоре сортирања спајањем.
BlokSort(niz) stepen_dvojke = CeoBrojStepenaDva(niz.size) skala = niz.size/stepen_dvojke // 1.0 ≤ skala < 2.0
// sortiranje umetanjem 16-31 elementa odjednom for (spajanje = 0; spajanje < stepen_dvojke; spajanje = spajanje + 16) pocetak = spajanje * skala kraj = (spajanje + 16) * skala SortiranjeUmetanjem(niz, [pocetak, kraj))
for (duzina = 16; duzina < stepen_dvojke; duzina = duzina * 2) for (spajanje = 0; spajanje < stepen_dvojke; spajanje = spajanje + duzina * 2) pocetak = spajanje * skala sred = (spajanje + duzina) * skala kraj = (spajanje + duzina * 2) * skala
if (niz[kraj- 1] < niz[pocetak]) // dva intervala su u obrnutom redosledu, tako da je rotacija dovoljna da ih spoji. Rotiraj(niz, sred - pocetak, [pocetak, kraj)) else if (niz[sred- 1] > niz[sred]) Spoji(niz, A = [pocetak, sred), B = [sred, kraj))
Фиксирани број цифара се такође може користити, приказивањем фактор скалирања као разломак:
stepen_dvojke = CeoBrojStepenaDva(niz.size) delilac = stepen_dvojke/16 deljenik_korak = niz.size % delilac dec_korak = sprat(niz.size/delilac)
[sortiranje umetanjem 16-31 elemenata odjednom]
while (dec_korak < niz.size) decimal = deljenik = 0 while (decimal < niz.size) // uzima opseg od A do B pocetak = decimal
decimal += dec_korak deljenik += deljenik_korak if (deljenik ≥ delilac) deljenik -= delilac decimal++
sred = decimal
decimal += dec_korak deljenik += deljenik_korak if (deljenik ≥ delilac) deljenik -= delilac decimal++
kraj = decimal
if (niz[kraj - 1] < niz[pocetak]) Rotiraj(niz, sred - pocetak, [pocetak, kraj)) else if (niz[mid - 1] > niz[sred]) Spoji(niz, A = [pocetak, sred), B = [sred, kraj))
deljenik_korak += deljenik_korak dec_korak += dec_korak if deljenik_korak ≥ delilac) deljenik_korak -= delilac dec_korak++
Издвајање бафера мини|десно|Процес избацивања бафера у блоксорту.
Два унутрашња бафера која су неопходна за сваки ниво спајања се креирају померањем првих 2 инстанци сваке вредности унутар једног подниза А са почетком А. Алгоритам прво итерира кроз елементе у А и пребројава јединствене вредности које му требају, затим ротира низ да би померио ове јединствене вредности на поцетак. Ако А није садржао довољно јединствених вредности да попуни два бафера (исте величине ), Б може исто тако добро да се користи. У овом случају помера се последња инстанца сваке вредности до краја Б, са преосталим Б делом који није био укључен током спајања.
while (decimal_korak < niz.size) blok_velicina = velicina = decimal_korak/blok_velicina + 1 [izbacuje dva bafera veličine 'bafer_size']
Ако Б не садржи довољно јединствених вредности, избацује се број са највећом јединственом вредношћу која је могла да се пронађе, затим подеси величину А и Б блока тако да број резултујућих А блокова је мањи или једнак броју избачених елемената (убачених на бафер). Само ће се један бафер користити у овом случају – други бафер неће ни постојати.
bafer_velicina = [pronađeni broj vrednosti] blok_velicina = decimal_korak/bafer_velicina + 1
decimal = deljenik = 0 while (decimal < niz.size) [uzima intervale od A i B] [podešava A i B da ne koriste intervale koje koriste baferi]
Означавање блокова мини|десно|Означавање А блокова помоћу вредности из првог унутрашњег бафера. Приметите да су први А блок и последњи Б блок различитих величина.
Једном када се један или два унутрашња бафера направе, започиње се спајање сваког А и Б подниза за овај ниво сортирања спајањем. Да би се десило све то, сваки А и Б подниз се дели на једнаке блокове једнаких величина, које су израчунате у претходном кораку, где су први А блок и последњи Б блок били различитих величина (ако је било потребно). Затим се креце кроз петљу за сваки А блок и замени другу вредност са одговарајућом вредношћу из првог унутрашњег бафера. Ово се назива означавање блокова.
// blokA je interval preostalih A blokova, // i prviA je A blok druge veličine blokA = [A.pocetak, A.pocetak + |blokA| % blok_velicina)
// zameni drugu vrednost svakog A bloka sa vrednošću u bafer1 for (index = 0, indexA = firstA.kraj + 1; indexA < blokA.kraj; indexA += blok_velicina) Zameni(niz[bafer1.pocetak + index], niz[indexA]) index++
poslednjiA = prviA blokB = [B.poceetak, B.pocetak + minimum(blok_velicina, |B|)) blokA.pocetak += |prviA|
Роловање и избацивање мини|десно|Два А блока се ролају кроз Б блокове. Једном када се први А бло избаци иза, блок А разлиците велицине се локално спаја са одговарајуцим Б вредностима. После дефинисања и означавање А блокова , А блокови су уролани (увијени) у Б блокове заменом првог А блока са следећим Б блоком. Овај процес се понавља све док је прва вредност А блока са најмањом означеном вредношћу мања или једнака последњој вредности Б блока-која је управо замењена са А блоком.
У том тренутку, најмањи А блок (А блок са најмањом означеном вредношћу) је замењен на почетак роловања А блокова а означена вредност постаје првобитна вредност из првог бафера. Ово се назива избацивање блока иза, пошто се неће више роловати са преосталим А блоковима. Затим се А блок умеће у претходни Б блок, прво се користи бинарна претрага на Б да би се нашло индекс где је прва вредност А мања или једнака елементу тог индекса од Б, и затим на том индексу ротирамо А у Б.
minA = blokA.pocetak indexA = 0
while (true) // ako postoji prethodni B blok i prva vrednost minimuma A bloka je ≤ // poslednja vrednost prethodnog B bloka, onda izbaci iza taj minimum A bloka. // ili ako nema preostalih B blokova onda nastavi da izbacujes preostaleA blokove. if ((|poslednjiB| > 0 and niz[poslednjiB.kraj - 1] ≥ niz[minA]) or |blokB| = 0) // pronaći gde da se podeli prethodni B blok, i rotirati ga oko sredine B_rascepljenje = BinarnaPrva(niz, niz[minA], lastB) B_ostatak = poslednjiB.kraj - B_rascepljenje
// Zameni minimum A bloka na početak rolanja A blokova blokZamena(niz, blokA.pocetak, minA, blok_velicina)
// vraća drugu vrednost za blok A Zameni(niz[blokA.pocetak + 1], niz[bafer1.pocetak + indexA]) indexA++
// rotira blok A oko prethodnog B bloka Rotiraj(niz, blokA.pocetak - B_rascepljenje, [B_rascepljenje, blokA.pocetak + blok_velicina))
// lokalno spajanje prethodnog A loka sa B vrednostima, // koristeći drugi unutrašnji bafer kao prostor za zamenu (ako postoji) if (|bafer2| > 0) SpajanjeUnutrasnje(niz, poslednjiA, [poslednjiA.kraj, B_rascepljenje), bafer2) else SpajanjeUMestu(niz, lastA, [poslednjiA.kraj, B_rascepljenje))
// ažuriraj raspon za preostale A blokove, // i preostali raspon od B se posle deli poslednjiA = [blokA.pocetak - B_ostatak, blokA.pocetak - B_ostatak + blok_velicina) poslenjiB = [poslednjiA.kraj, poslednjiA.kraj + B_ostatak)
// ako ne postoji više preostalih A blokova, ovaj korak je završen onda blokA.pocetak = blokA.pocetak + blok_velicina if (|blokA| = 0) break
minA = [novi minimum A bloka] (pogledaj ispod) else if (|blokB| < blok_velicina) // pomeranje poslednjeg B bloka, koji je druge veličine, // do prethodno preostalih A blokova pomoću rotacije Rotiraj(niz, blokB.pocetak - blokA.pocetak, [blokA.pocetak, blokB.kraj))
poslednjiB = [blokA.pocetak, blokA.pocetak + |blokB|) blokA.pocetak += |blokB | blokA.kraj += |blokB | minA += |blokB | blokB.kraj = blokB.pocetak else // rolanje skroz levog A bloka na kraj pomoću zamene sa sledećim B blokom blokZamena(niz, blokA.pocetak, blokB.pocetak, blok_velicina) poslednjiB = [blokA.pocetak, blokA.pocetak + blok_velicina) if (minA = blokA.pocetak) minA = blokA.kraj
blokA.pocetak += blok_velicina blokA.kraj += blok_velicina blokB.pocetak += blok_velicina
<span style="color:green;">// ovo je ekvivalentno minimumu (blokB.kraj + blok_size, B.kraj),</span> // ali ima potenciju da ima prekoračenje if (blokB.kraj > B.kraj - blok_velicina) blokB.kraj = B.kraj else blokB.kraj += blok_velicina
// spajanje poslednjeg A bloka sa preostalim B vrednostima if (|bafer2| > 0) SpajanjeUnutrasnje(niz, poslednjiA, [poslednjiA.kraj, B.kraj), bafer2) else SpajanjeUMestu(niz, poslednjiA, [poslednjiA.kraj, B.kraj))