Смутсорт
 | Овај чланак можда захтева чишћење и/или прерађивање како би се задовољили стандарди квалитета Википедије. Проблем: Додати унутрашње везе, изворе итд.. (фебруар 2018) |
 | ||||||||||
|
Smutsort (engl. Smoothsort - глатко сортирање) је алгоритам за сортирање који је заснован на поређењу елемената.[1] То је облик хипсорта који је развио Едсгер Дијкстра
Као и хипсорт, глатки сорт је сложености О(нлогн). Предност смутсорта је што је ближи сложености О(н) ако је улаз до неке мере већ сортиран, а хипсорт је просечне сложености О(нлогн) без обзира на то колико је улаз сортиран.
Преглед[уреди | уреди извор]
Као и хипсорт, смутсорт гради структуру података која се назива хип за низ који треба да се сортира, затим сортира низ сталним вађењем највећег елемента из хипа. За разлику од хипсорта, смутсорт не користи бинарни хип, већ онај који је заснован на Леонардовим бројевима.
Структура хип се састоји од низа у коме су сви чланови величине Леонардових бројева и чији су корени у растућем редоследу. Предност оваквог хипа у односу на бинарни је, ако је низ већ сортиран, онда је сложеност конструисања и деконструисања хипа О(н). Разбијање улаза у низ је једноставно-крајње леви члан се поставља у могући хип и остатак је такође подељен. Може се доказати да:
- Било који низ, било које дужине може бити подељен у делове величине L(x).
- Никоја два хипа неће имати исту величину, због тога ће низ бити строго низ хипова опадајуће величине.
- Никоја два хипа неће бити величине два узастопна Леонардова броја, осим можда последња два.
Сваки хип који је величине L(x) је грађен с лева на десно као суб-хип величине L(x-2) и корен. Изузеци су хипови величине L(1) и L(0) који имају по један чвор. Сваки хип одржава својство да је корен увек већи или једнак од синова. Последица овога је да је чвор који је на десном крају низа увек највећи од свих и, што је важно, да низ који је већ сортиран не мора поново да се сортира. Ово је разлог добре сложености алгоритма.
Алгоритам је једноставан. Почиње се тако што се несортирани низ дели на хипове од једног елемента. Низ од једног елемента је тривијалан хип. Овај низ расте тако сто се са десне стране додаје по један елемент и уједно се врши замена места елемената уколико није задовољено својство хипа све док се не попуни низ.
Од овог тенутка елемент на десном крају низа биће највећи и биће на свом месту. Затим смањујемо серије хипа назад до једног елемента уклањајући чвор који је на десном крају и правећи нови распоред како би се одржао услов хипа. Када смо стигли до последњег хипа, низ је сортиран.
Операције[уреди | уреди извор]
Операције које су неопходне су повећање низа додавањем једног елемента са десне стране и смањење низа уклањањем десног елемента (корена последњег хипа) чувајући услове хипа и низа.
Увећавање низа додавањем елемента здесна[уреди | уреди извор]
- Ако су последња два хипа величине L(x+1) и L(x), нови елемент постаје корен већег хипа величине L(x+2); овај хип не мора нужно имати својства хипа.
- Ако последња два хипа нису узастопни Леонардови бројеви, онда елемент који је на десном крају постаје нови хип величине 1,ова 1 је узета из L(1), осим ако је хип на десном крају величине L(1), онда је нови елемент хипа величине L(0).
После овога, својства хипа и низа морају да се врате што се углавном ради сортирањем уметањем. То се ради на овај начин:
- Хип на десном крају (који је управо креиран) постаје тренутни хип
- Док постоји хип са леве стране тренутног хипа и његов корен је већи од тренутног корена и оба његова сина онда се замене нови корен и корен хипа са леве стране; овакав хип постаје тренутни
- Извршава се "филтрирање" на тренутним хипу док се не утврди својство хипа
Док је тренутни хип већи од 1 или син третнутног хипа има веци корен од корена тренутног хипа: мења се већи син са тренутним кореном, тај син постаје тренутни хип. Филтрирање је увелико поједностављено коришћењем Леонардових бројева тако што ће хип имати или један чвор или два сина. Не мора се водити рачуна да ли постоје оба сина.
Смањење низа уклањањем десног хипа[уреди | уреди извор]
Ако је десни хип величине 1 (нпр. L(1), L(0)), онда не треба нисшта да се ради. Само се уклони тај хип. Ако десни хип није величине 1, онда се уклања корен и враћа се својство низа, прво левог па десног.
Искоришћеност меморије[уреди | уреди извор]
Смутсорт мора да чува у меморији све хипове у низу. С обзиром да су све ове вредности различите, ово се постиже коришћењем битских вектора.
Јава имплементација[уреди | уреди извор]
// odrzavanjem ovih konstanti, izbegava se zamoran posao
// cuvanja Dijkstrinih a i b. Umesto njih, indekse cuvamo
// u ovom nizu.
static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
866988873 // the next number is > 31 bits.
};
public static <C extends Comparable<? super C>> void sort(C[] m,
int lo, int hi) {
int head = lo; // the offset of the first element of the prefix into m
// Ove promenljive zahtevaju malo objasnjenja. Ako je niz hipova velicine
// 38, onda ce hip biti velicine 25+9+3+1, sto su Leonardovi brojevi
// 6, 4, 2, 1.
// Pretvaranjem ovih u binarne brojeve, dobija se b01010110 = 0x56. Predstavljamo
// ove brojeve kao par brojeva desno popunjenim nulama i
// skladistenjem mantise i eksponenta kao "p" i "pshift".
// Ovo je zgodno, jer eskponent indeks L[] daje velicinu desnog hipa
// i zato sto se odmah moze znati da li su poslednja dva hipa uzastopni Leonardovi
// brojevi proveravanjem (p&3)==3
int p = 1;
int pshift = 1;
while (head < hi) {
if ((p & 3) == 3) {
sift(m, pshift, head);
p >>>= 2;
pshift += 2;
} else {
if (LP[pshift - 1] >= hi - head) {
trinkle(m, p, pshift, head, false);
} else {
sift(m, pshift, head);
}
if (pshift == 1) {
p <<= 1;
pshift--;
} else {
p <<= (pshift - 1);
pshift = 1;
}
}
p |= 1;
head++;
}
trinkle(m, p, pshift, head, false);
while (pshift != 1 || p != 1) {
if (pshift <= 1) {
int trail = Integer.numberOfTrailingZeros(p & ~1);
p >>>= trail;
pshift += trail;
} else {
p <<= 2;
p ^= 7;
pshift -= 2;
// Ovaj blok se razbija na binarno drvo. Bit na desnom kraju
// je blok suzine 1. Levi deo je podeljen na dva: blok duzine LP[pshift+1]
// i LP[shift].
trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
trinkle(m, p, pshift, head - 1, true);
}
head--;
}
}
private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
int head) {
C val = m[head];
while (pshift > 1) {
int rt = head - 1;
int lf = head - 1 - LP[pshift - 2];
if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
break;
if (m[lf].compareTo(m[rt]) >= 0) {
m[head] = m[lf];
head = lf;
pshift -= 1;
} else {
m[head] = m[rt];
head = rt;
pshift -= 2;
}
}
m[head] = val;
}
private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
int pshift, int head, boolean isTrusty) {
C val = m[head];
while (p != 1) {
int stepson = head - LP[pshift];
if (m[stepson].compareTo(val) <= 0)
break; // current node is greater than head. Sift.
if (!isTrusty && pshift > 1) {
int rt = head - 1;
int lf = head - 1 - LP[pshift - 2];
if (m[rt].compareTo(m[stepson]) >= 0
|| m[lf].compareTo(m[stepson]) >= 0)
break;
}
m[head] = m[stepson];
head = stepson;
int trail = Integer.numberOfTrailingZeros(p & ~1);
p >>>= trail;
pshift += trail;
isTrusty = false;
}
if (!isTrusty) {
m[head] = val;
sift(m, pshift, head);
}
}
Референце[уреди | уреди извор]
- ^ Дијкстра, Едсгер W. Смоотхсорт – ан алтернативе то сортинг ин ситу (ЕWД-796а). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион)