Hledam maximalni hodnotu, tak, ze postupne porovnavam a vymenuji s nasledujici. Totez opakuji pro dalsi hodnotu.
7_ 2_ \7_ \3_ 2_/ \7_ 3_/ \5_ 3____/ \7_ 5____/ \6_ 5_______/ \7_ 6_______/ \6_ 6__________/ \7_ 0__________/ \6_ 0_____________/ \7_ 1_____________/ \_6 1________________/ \_7 4________________/ 4___________________/ - 7 2 2 2 2 2 2 0 0 0 0 2 73 3 33 3 33 30 21 11 1 1 3 75 5 55 5 50 31 22 2 2 5 76 6 60 0 51 33 3 3 6 70 0 61 1 54 4 4 0 71 1 64 4 5 5 1 74 4 6 - 6 4 7 - - 7
var i, i_end, j, j_start, j_end;
j_start = start;
i_end = end;
j_end = end - start - 1;
i = start + 1;
while (i<i_end)
{
j = j_start;
while (j<j_end)
{
if (cmp(list[j], list[j+1]))
{
swap(list, j, j+1);
}
j++;
}
j_end--;
i++;
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 198 compares ~ 523.776 cycles ~ 784.338 moves ~ 524.799 stability = stableTop
Hledam maximalni hodnotu, tak, ze postupne porovnavam a vymenuji s nasledujici. Totez opakuji pro dalsi hodnotu, ale hledam minimum a postupuji od konce. (oproti Bubble sort by se mel snizit pocet presunu hodnot)
7_ 2________________ \2 3_____________ \0* 2_/7-\3 5__________ \0_/2 3____/7-\5 6_______ \0_/3 5_______/7-\6 0____ \0_/5 6__________/7-\0 1_ \0_/6 0_____________/7-\1 \1_/1 1________________/7-\_4 4_/4 4___________________/ 7* - 7 2 2 0 0 2 73 3 02 2 1 1 3 75 5 03 33 12 2 2 2 5 76 6 05 55 13 33 33 3 6 70 0 06 61 15 54 4 4 0 71 1 11 64 4 5 5 1 74 4 4 6 6 4 7 - 7
var i, i_start, i_end, swapped;
i_start = start;
i_end = end - 1;
swapped = true;
while (swapped == true)
{
swapped = false;
for (i = i_start; i<i_end; i++)
{
if (cmp(list[i], list[i+1]))
{
swapped = swap(list, i, i+1);
}
}
if (swapped == false) {break;}
i_end--;
swapped = false;
for (i = i_end; i >= i_start; i--)
{
if (cmp(list[i], list[i+1]))
{
swapped = swap(list, i, i+1);
}
}
i_start++;
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 160 compares ~ 399.048 cycles ~ 784.338 moves ~ 398.787 stability = stableTop
Zvolim si posledni hodnotu jako Pivot. Porovnam s nim vsechna ostatni ve skupine. Mensi dam pred
nej, vetsi za nej. Pak si zvolim pivota ze skupine mensich cisel a porovnam je s nim.
A pak pivota ve skupine vetsich cisel a porovnam je s nim. Opakuji.
Nevyhoda - DESC serazeny seznam (od nejvetsiho cisla po nejmensi) se serazuje stejne pomalu
jako Bubble sort. To lze resit treba nahodnym vyberem pozice Pivota nebo porovnat sousedni hodnoty
a zjistit, kolik je serazenych ASC, DESC (nebo ted experimentuji se serazeni seznamu po dvou
prvcich pred spustenim Quick sortu).
lo<4<hi Lo<1<Hi LO<3<HI
7_ lo 2_ Lo 0 0
2 |_ 3 |_ - 1
3 | |_ 0 | |_ Hi 2_ LO 2 2
5 | | |_ 1_|_|_| 3_| - 3
6 | | | |_ - 4
0 | | | | |_ hi 7_______ lO 5 5
1 | | | | | |_ 5 |_ - 6
4_|_|_|_|_|_|_| 6_______|_| hI 7 7
lO<6<hI
7 7 2 2 0 - 0
2 2 3 3 -1 - 1
3 3 0 0 2 2-2
5 5 1*111 3 *3 3
6 6 - 4
0 0 7 7 5 5
1 1 5 5 -6 6
4*4444444 6 *66 7 7
function BubblingQuickPart(list, low, high, cmp, swap)
{
var pivot, i,j;
pivot = list[high];
i = low;
for (j = low; j < high; j++)
{
if (cmp(pivot, list[j]))
{
swap(list, i, j);
i++;
}
}
swap(list, i, high);
return i;
}
function BubblingQuickSort(list, start, end, cmp, swap)
{
if (start < end)
{ cyclesAdd();
var index = BubblingQuickPart(list, start, end, cmp, swap);
BubblingQuickSort(list, start, index-1, cmp, swap);
BubblingQuickSort(list, index+1, end, cmp, swap);
}
return list;
}
list = BubblingQuickSort(list, start, end-1, cmp, swap);
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 15 compares ~ 12.496 cycles ~ 13.227 moves ~ 19.692 stability = noTop
Najdi pozici nejmensiho cisla a vymeni vymen cisla na teto a prvni pozici (pokud nejsou pozice stejne).
7 7 *0 - - - 0 2 22 2 2 *1 - - 1 3 32 3 32 3 3 *2 - 2 5 52 5 52 5 53 5 5 *3 3 6 62 6 62 6 63 6 65 6 6 *4 4 0 00 *7 72 7 73 7 75 7 76 7 7 *5 5 1 10 1 11*2 22*3 33*5 55 5 55*7 7* 6 4 4 4 4 4 4 4 4 4 4*6 6 6 6* 7
var i, i_end, j, j_end, tmp_pos;
i_end = end - 1;
j_end = end;
i = start;
while (i<i_end)
{
j = i + 1;
tmp_pos = i;
while (j<j_end)
{
if (cmp(list[tmp_pos], list[j])) {tmp_pos = j;}
j++;
}
swap(list, i, tmp_pos);
i++;
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 104 compares ~ 523.776 cycles ~ 524.799 moves ~ 3.048 stability = noTop
Urcim nejmensi prvnich dvou, nejmensi druhych dvou. Porovnam obe nejmensi a urcim tim nejmensi ze ctyr. A totez udelam pro dalsi ctverici a zas porovnam jejich nejmensi. A urcim tak nejmensi z osmi... Az ziskam nejmensi z nejmensich. Pak ho vyradim z vyherni listiny a postoupi misto nej dalsi v jeho vetvi. A je pak nutno zjistit, ktere dalsi vetve to ovlivni a opet ziskam nejmensi. Ale, s kodem to neni tak jednoduche, kdyz si musime pamatovat, ktere je v kazde vetvi mensi (a dalsi komplikace nastava s lichym poctem polozek)
7_ __ __
\2_ \__ \__ 7_ 7_ __
2_/ \ __/ \ __/ \ \ \ \
3_ 2- __ 2- __ 2- __ 3- 5- 5- 7-
\3_/ \ \__/ \ \__/ \ \3_/ \ 5_/ \ __/ \ \
5_/ \ __/ \ __/ \ __/ \ \ \ \
\_0 \_1 \_2 \_3 \_4 \_5 \_67
6_ / / / / / / /
\0_ / 6_ / 6_ / __ / __ / / /
0_/ \ / \ / \ / \ / \ / / /
1_ 0- __ 1- 4- 4- 4- 6- 6-
\1_/ \1_/ 4_/ __/ __/
4_/ __/
// build first pyramid of minimal values
function pyramid_part1_buildPyramid(list, i_start, i_end, size, cmp, swap)
{
var i,j,k, k_end, lvl, lvlp1;
var pyramid = [];
i = i_start;
j = i_start+1;
k = 0;
lvl = 0;
pyramid[lvl] = [];
while (j<i_end)
{
if (cmp(list[i], list[j]))
{swap(list, i, j);}
pyramid[lvl][k] = i; i+=2; j+=2; k++;
}
if (i<i_end) // pokud je size liche cislo, pak pridej posledni prvek a preswapuj to
// (toho vyuziji pozdeji v part2)
{
if (cmp(list[i-2], list[i]))
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = list[i-2];
list[i-2] = tmp; movesAdd(4);
pyramid[lvl][k] = i;
}
else {if (cmp(list[i-1], list[i]))
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = tmp; movesAdd(3);
}}
}
i_end = k;
lvlp1 = lvl + 1;
while (i_end>1)
{
pyramid[lvlp1] = [];
k = 0;
i = 0;
j = 1; // =i+1
while (j<i_end)
{
if (cmp(list[ pyramid[lvl][i] ], list[ pyramid[lvl][j] ]))
{pyramid[lvlp1][k] = pyramid[lvl][j]; i+=2; j+=2; k++; continue;}
else {pyramid[lvlp1][k] = pyramid[lvl][i]; i+=2; j+=2; k++; continue;}
}
if (i<i_end) {pyramid[lvlp1][k] = pyramid[lvl][i]; k++;}
lvl++;
lvlp1++;
i_end = k;
}
return [pyramid, lvl, pyramid[lvl][0], (size>>1)<<1 != size];
// return pyramid, last lvl, last index, boolean for odd-size)
}
function pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos)
{
var lvl, val2, empty = -1, a, b;
val2 = pyramid[0][pos];
for (lvl=0; lvl<lvl_end; lvl++)
{
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2;
continue;
}
b = pyramid[lvl][pos+1];
a = pyramid[lvl][pos];
pos = pos>>1;
if (b==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
}
return [pyramid, lvl_end, pyramid[lvl_end][0], bool];
}
// rebuild pyramid, rewrite branch by new value
function pyramid_part2_rebuildPyramid(pyramid, lvl_end, bool, list, cmp, i_end, i_endm3)
{
var cycles = 0;
var lvl, pos, val, val2, a, b, empty=-1;
val = pyramid[lvl_end][0];
pos = val>>1; // pozice zleva
if (bool==true && ((pos<<1)==i_endm3) && ((val & 0x01) == 0) )
// kdyz je size liche cislo a dojde k eliminaci n-2, tak posun posledni 2 cisla
{
bool = false;
list[val] = list[val+1];
list[val+1] = list[val+2]; movesAdd(2);
// je sude, pak vymen za liche a prepocitej porovnani
// (prepocitej vsechna nutna porovnani)
pyramid[0][pos] = val;
// pozn.: tento kod je prepsany na funkci, protoze by byl duplicitne
return
pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos);
}
else {if ((val & 0x01) == 0) // je sude, pak vymen za liche a prepocitej porovnani
{
pyramid[0][pos] = val + 1;
return pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos);
}
else { // je liche, pak odstran a prepocitej porovnani
val2 = empty;
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_end; lvl++)
{
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2
continue;
}
a = pyramid[lvl][pos];
b = pyramid[lvl][pos+1];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (b!==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a;
val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (a!==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
pyramid[lvl+1][pos] = b;
val2 = b;
}
}
}}
return [pyramid, lvl_end, pyramid[lvl_end][0], bool];
}
// princip: vyber minimum z kazdeho paru, pak porovnej minima, minima minim ... az ziskas nejmensi cislo
// pak vyrad nejmensi cislo z pyramidy a propocitej celou vetev, opet ziskej minimum
function PyramidSelectSort(list, start, end, cmp)
{
var pyramid_data, i, x, y, endm3 = end-3, size = end - start;
x = list;
y = [];
pyramid_data = pyramid_part1_buildPyramid(x, start, end, size, cmp, swap);
// create pyramid of index from minimal values of pair
i = start;
y[i] = x[pyramid_data[2]]; movesAdd(1);
i++;
while (i<end)
{
pyramid_data = pyramid_part2_rebuildPyramid(
pyramid_data[0], pyramid_data[1], pyramid_data[3], x, cmp, end, endm3);
y[i] = x[pyramid_data[2]]; movesAdd(1);
i++;
}
return y;
}
list = PyramidSelectSort(list, start, end, cmp);
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 15 compares ~ 8.933 cycles ~ 11.262 moves ~ 1.732 stability = stableTop
Vyberu hodnotu a vkladam ji do serazeneho pole ze shora (nebo ze spodu). Kdyz je pole serazene, tak se zastavim na prvni vyssi hodnote.
7\ 2_ 2_ 2_ 2_ 0_ 0_ 0 2/ 7_\ 3_\ 3_\ 3 \ 2_\ 1_\ 1 3 3 7_\\ 5_\\ 5 \ 3 \\ 2_\\ 2 5 5 7_\\\ 6 \ 5 \\ 3_\\\ 3 6 6 7 \ 6 \\ 5_\\\\ 4 0 0 7 \\ 6 \\\\\ 5 1 1 7 \\\\\ 6 4 4 7
var i, i_end, j, j_end, j2, tmp;
i_end = end;
j_end = start;
i = start + 1;
j = start;
j2 = start + 1;
while (i<i_end)
{
tmp = list[i]; movesAdd(1);
while (j>=j_end && cmp(list[j], tmp)) // prohledavej od konce
{
list[j2] = list[j];
j2--;
j--; movesAdd(1);
}
list[j2] = tmp; movesAdd(1);
j = i;
i++;
j2 = i;
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 89 compares ~ 262.465 cycles ~ 263.492 moves ~ 262.469 stability = stableTop
Vyberu hodnotu a vkladam ji do serazeneho pole od stredu (poloviny delky serazene casti,
do ktere patri). Kdyz je pole serazene, tak se zastavim kdyz hodnota nad je mensi nebo
rovna a hodnota pod je vetsi.
Pozn. Muj js-kod pocita stred trochu odlisne (spis spodni hodnotu), je to pro zjednoduseni kodu.
7\ 2_ 2 2 2_ 0_ 0
2/ 7_\ 3_ 3_ 3 \ 2_\_ 1
3 3 7_\ 5_\ 5_ \ 3_ \\ 2
5 5 7_\\ 6 \ \ 5 \ \\ 3_
6 6 7 \ \ 6 \ \\ 5_\__
0 . 0 7 \ \\ 6__\_\
1 . 1 7 \\\
4 . 4
v 50% delky (23567) je hodnota 5, hodnota 0 je mensi nez 5
v 50% delky mensich hodnot nez 5 (23) je hodnota 2, 0 je mensi nez 2
(v pripade 50% ze dvou hodnot, porovnavam s horni hodnotou)
var i, i_end, left, right, mid, mid_sub;
i_end = end;
i = start + 1;
while (i<i_end)
{
// find position in sorted list
left = start - 1;
right = i;
mid_sub = right - left;
while (true)
{
mid = left + (mid_sub>>1);
if (cmp(list[mid], list[i]))
{
right = mid;
mid_sub = right - left;
if (mid_sub<=1) {break;}
}
else {
left = mid;
mid_sub = right - left;
if (mid_sub<=1) {mid++; break;}
}
}
// move from position old to new
arrayShift(list, mid, i);
i++;
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 47 compares ~ 8.850 cycles ~ 271.319 moves ~ 261.446 stability = stableTop
Jedna se o spojovani serazenych seznamu porovnavanim hornich hodnot z obou seznamu. Na zacatku maji vsechny serazene seznamy delku 1.
7_ | 2 _ 2_| 7 |_ _ 2_ _ _ 3_ | | | 3 | | |_ 0 | 3 _|_| | 5 | | | |_ _ 1 5_| 5 _____| 7 | | | | | |_ 2 6_ | | | | | | | 3 | 0 _ 0_| | | | | | | 4 0_| 6 |_ _ 1___| | | | | | 5 1_ | | | 4_____|_|_| | | 6 | 1 _|_| | 6___________|_| 7 4_| 4 _____|
function sortListMerge_m2_v2_Top(list, start, end, size, cmp)
{
var step, step_double, tmp, a,b,c, i,j,k,
step_max = ((size + 1) >> 1) << 1,
arr = [ list, [] ],
m = 0,
n = 1;
for (step=1; step<step_max; step=step_double) // bounds 1-1, 2-2, 4-4, 8-8...
{
a = start;
step_double = step<<1;
while (a<end)
{
b = a + step;
c = a + step_double;
b = b<end ? b : end;
c = c<end ? c : end;
arrayMerge(arr[m], a, b, b, c, arr[n], a, cmp);
a = c;
}
tmp = m; m = n; n = tmp;
}
return arr[m];
}
list = sortListMerge_m2_v2_Top(list, start, end, size, cmp)
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 5 compares ~ 8.933 cycles ~ 11.273 moves ~ 10.240 stability = stableTop
Jedna se o spojovani serazenych seznamu porovnavanim hornich hodnot z obou seznamu. Na zacatku zjistim serazene seznamy porovnanim dvou sousednich hodnot.
7_ 7_ _ _ _
2_|_ | | | | 2_ _ _
3___|_ 2_| | | | 3 | | |_ 0
5_____|_ 3___| | | 5 | | | |_ 1
6_______|_ 5_____| | 6 | | | | | 2
0_________|_ 6_______| 7 | | | | | 3
1___________|_ | | | | | 4
4_____________| 0 0_| | | | | 5
1 1___| | | | 6
4 4_____|_|_| 7
// pozn.: Mohl jsem pri prepisovani kodu udelat chyby.
function XsortListMerge_m2x_v1_Top_Bounds(list, start, end, size, cmp)
{
var i, x, y, j, tmp, cp, desc, arr, b, bounds = [];
desc = 0;
b = 0;
bounds[b++] = start;
for (i=start+1; i<end; i++)
{
cp = cmp(list[i-1], list[i]);
if (cp>0)
{bounds[b++] = i; desc++; continue;}
if (cp>=0)
{desc++;}
}
bounds[b] = end;
if (b==1)
{return list;} // asc, a<=b<=c...
if (b==size)
{return sortOrderDesc(list, start, end, cmp);} // desc, a>b>c...
if (desc==size)
{return sortOrderDescStable(list, start, end, cmp);} // desc, a>=b>=c...
arr = [ list, [] ];
x = 0;
y = 1;
while (true)
{
for (i=0; i<=b-2; i+=2)
{
arrayMerge(arr[x], bounds[i], bounds[i+1], bounds[i+1], bounds[i+2],
arr[y], bounds[i], cmp);
}
if (i<b)
{
arrayCopy(arr[x], bounds[i], bounds[i+1], arr[y], bounds[i]);
}
if (b<=2) {break;}
b = b >> 1;
for (i=0; i<=b; i++)
{
bounds[i] = bounds[i<<1];
}
b++;
bounds[b] = end;
tmp = x; x = y; y = tmp;
}
return arr[x];
}
list = XsortListMerge_m2x_v1_Top_Bounds(list, start, end, size, cmp);
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 40 compares ~ 10.390 cycles ~ 13.352 moves ~ 11.264 stability = stableTop
Counting sorty ukladaji do pometi hodnotu + pocet stejnych hodnot. A pak je vypisi v poradi.
Vyhodne jsou pro hodnoty typu integer (4 bytes) nebo pro hodnoty, ktere dokazeme popsat
zjednodusene. Cili, treba pro dlouhe textove hodnoty by bylo treba spoustu pameti a cyklu.
Nejcastejsi rozdelovani je podle bitu, bytu, digitu (cifer)...
Pigehole Sort - pocita pocet stejnych hodnot
7 2 3 5 6 0 1 4
7 min:0 . . . . . 0:1x. 0:1x 0
2 max:7 . . . . . 1:1x 1:1x 1
3 . 2:1x. . . 2:1x 2
5 . 3:1x. . 3:1x 3
6 . . . 4:1x 4:1x 4
0 . 5:1x 5:1x 5
1 . 6:1x 6:1x 6
4 7:1x 7:1x 7
--
3 2 3 3 1 0 1 1
3 min:0 . . . . . 0:1x. 0:1x 0
2 max:3 . . . . 1:1x. . 1:3x 1
3 . . . . 1:2x 2:1x 1
3 . . . . 1:3x 3:3x 1
1 . 2:1x. 2
0 3:1x. . 3
1 3:2x 3
1 3:3x 3
var bucket, idx, i, b_start, b_end;
bucket = [];
b_start = list[start];
b_end = list[start]; movesAdd(2);
for (i=start; i<end; i++)
{
if (typeof bucket[list[i]]!=='undefined') {bucket[list[i]]++;} else {bucket[list[i]] = 1;}
if (cmp(b_start,list[i])) {b_start = list[i]; movesAdd(1);} // min value
if (cmp(list[i],b_end)) {b_end = list[i]; movesAdd(1);} // max value
}
idx = 0;
for (i=b_start; i<=b_end; i++)
{
if (typeof bucket[i]=='undefined')
{continue;}
while (bucket[i]>0)
{
list[idx++] = i; movesAdd(1);
bucket[i]--;
}
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 3 compares ~ 2.048 cycles ~ 2.560 moves ~ 1.465 stability = stableTop
Counting sorty ukladaji do pometi hodnotu + pocet stejnych hodnot. A pak je vypisi v poradi.
Vyhodne jsou pro hodnoty typu integer (4 bytes) nebo pro hodnoty, ktere dokazeme popsat
zjednodusene. Cili, treba pro dlouhe textove hodnoty by bylo treba spoustu pameti a cyklu.
Nejcastejsi rozdelovani je podle bitu, bytu, digitu (cifer)...
RadixLSD Sort - pocita pocet stejnych desitkovych cifer z hodnot
7 2 3 5 6 0 1 4
7 min:0 . . . . . 0:1x. 0:1x 0
2 max:7 . . . . . 1:1x 1:1x 1
3 . 2:1x. . . 2:1x 2
5 . 3:1x. . 3:1x 3
6 . . . 4:1x 4:1x 4
0 . 5:1x 5:1x 5
1 . 6:1x 6:1x 6
4 7:1x 7:1x 7
--
3 2 3 3 1 0 1 1
3 min:0 . . . . . 0:1x. 0:1x 0
2 max:3 . . . . 1:1x. . 1:3x 1
3 . . . . 1:2x 2:1x 1
3 . . . . 1:3x 3:3x 1
1 . 2:1x. 2
0 3:1x. . 3
1 3:2x 3
1 3:3x 3
var i, i_end, j, j_end, b_index, pos,
bucket = [[]],
mod = 10,
dev = 1,
value_max = Math.max(...list), // pozn. tuto cast resi pole a rekneme, ze nezatici alg.
i_end = Math.ceil(Math.log10(value_max + 1)); // maxDigitSymbolsOfValue
for (i = 0; i < i_end; i++, dev *= 10, mod *= 10)
{
for (j = start; j < end; j++)
{
b_index = parseInt((list[j] % mod) / dev); comparesAdd(1);
if (typeof bucket[b_index]==='undefined')
{
bucket[b_index] = [];
}
bucket[b_index].push(list[j]); movesAdd(1);
}
pos = 0;
j_end = bucket.length;
for (j = 0; j < j_end; j++)
{
if (typeof bucket[j]!=='undefined')
{
i_end = bucket[j].length;
for (i = 0; i < i_end; i++)
{
list[pos++] = bucket[j].shift(); movesAdd(1);
}
}
}
}
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 9 compares ~ 3.072 cycles ~ 6.144 moves ~ 6.144 stability = stableTop
Pozn.: Vypada podobny Quick sortu, melo by to byt rychlejsi pro HW.
Pozn.: Udajne je to varianta Tournament sortu.
create position tree 7 a a 2 b / \ 3 c / \ 5 d b c 6 e / \ / \ 0 f d e f g 1 g / 4 h h
function heapHeapify_part(list, i, N, cmp, swap)
{ cyclesAdd();
var largest = i; // Initialize largest as root
var left = 2 * i + 1; // left = 2*i + 1
var right = 2 * i + 2; // right = 2*i + 2
if (left < N && cmp(list[left], list[largest]))
largest = left;
if (right < N && cmp(list[right], list[largest]))
largest = right;
if (largest != i)
{
swap(list, i, largest);
heapHeapify_part(list, largest, N, cmp, swap);
}
return list;
}
function heapSort(list, start, end, size, cmp, swap)
{
var N = size;
for (var i = Math.floor(N / 2) - 1; i >= 0; i--)
heapHeapify_part(list, start+i, start+N, cmp, swap)
for (var i = N - 1; i > start; i--)
{
swap(list, i, start);
heapHeapify_part(list, start, start+i, cmp, swap);
}
return list;
}
list = heapSort(list, start, end, size, cmp, swap); // https://www.geeksforgeeks.org/heap-sort/
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 13 compares ~ 17.338 cycles ~ 10.370 moves ~ 28.035 stability = noTop
Pozn.: Vypada podobne jako Quick sort, ale je vyhodnejsi integraci do HW, protoze pouziva
stejny postup operaci.
Zajimave je, ze cisla compares, cycles, moves klidne kolisaji o +-50% a cas ani ne.
7_______ 6 6_________ 3 3___________ 1 1_____________ 0 0 2_____ | 0 0_______ | 0 0_________ | 0 0___________ _| 01 1 3___ | | 1 1_____ | | 1 1_______ |_| 1 3 3_________ _| 22 2 5_ | | | 4 4___ | |_| 3 6 6_____ |_| 2 2 2_______ _| 23 3 6 | | |_| 7 7_ | |_| 5 5 5___ |_| 4 4 4_____ _| 44 4 0 | |_| 2 2 | |_| 2 2_ |_| 2 6 6___ _| 55 5 1 |_| 3 3 |_| 4 4 |_| 5 5_ _| 56 6 4_| 5 5_| 7 7_| 7 7_| 7 7
// pozn. Kod jsem mohl pri prepisovani poskodit.
function shellWithGap(list, start, end, gap, cmp)
{
var i, currentvalue, position;
for (i=start+gap; i<end; i+=gap)
{
currentvalue = list[i]; movesAdd(1);
position = i;
while (position>=gap && cmp(list[position-gap],currentvalue))
{
list[position] = list[position-gap]; movesAdd(1);
position = position - gap;
}
list[position] = currentvalue; movesAdd(1);
}
}
function sortShell(list, start, end, cmp)
{
var sublistcount, startposition;
sublistcount = (start + end)>>1;
while (sublistcount > 0)
{
for (startposition=start; startposition<sublistcount; startposition++)
{
shellWithGap(list, startposition, end, sublistcount, cmp);
}
sublistcount = sublistcount>>1;
}
return list;
}
list = sortShell(list, start, end, cmp);
test repeat = 10 times (on cpu from 2009) test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of n, array with repeating values) ------------------------ time ~ 8 compares ~ 31.234 cycles ~ 23.546 moves ~ 40.957 stability = noTop
list.sort(cmp);
test repeat = 10 times (on cpu from 2009) n = 1.024 value = 0 to 511 (n/2, 50% of array with repeating values) ---------------------- time ~ 11 compares ~ 9.244 cycles ~ ? moves ~ ? stability = ?Top
Pozor, vsechny merene hodnoty slouzi jen jako orientacni!
Merene hodnoty
Problemy pri mereni
Tipy
Funkce pouzite v algoritmech
// only for statistic info about moves, cycles, compares
function movesAdd(a) {glob.moves += a;};
function cyclesAdd() {glob.cycles++;};
function comparesAdd() {glob.cmps++;};
// others
function swap(list, a, b)
{
if (a!=b) {var tmp = list[a]; list[a] = list[b]; list[b] = tmp; movesAdd(3); return true;}
return false;
}
function cmp(a, b) {comparesAdd(); return a>b;}
function cmp2(a, b) {comparesAdd(); return a - b;} // when you need get state ==, >, <
function move(a, b) {app2.s.glob.moves++; a = b;}
// reverse array - unstable sort
function sortOrderDesc(list, lo, hi)
{
var tmp;
hi--; cyclesAdd(hi - lo); movesAdd(3*(hi - lo));
while (lo < hi)
{
tmp = list[lo];
list[lo++] = list[hi];
list[hi--] = tmp;
}
return list;
}
// reverse array - stable sort
function sortOrderDescStable(list, start, end, cmp)
{
var a, b, c, lo, hi;
lo = start;
hi = end - 1;
// find equal values and swap it
while (lo < hi)
{
a = lo;
b = lo;
c = lo;
while (b<hi && cmp(list[b++], list[b])==0)
{
c++;
}
lo = c+1;
cyclesAdd((c - a)>>1); movesAdd(3*(c - a)>>1);
while (c>a)
{
tmp = list[a];
list[a++] = list[c];
list[c--] = tmp;
}
}
list = sortOrderDesc(list, start, end);
return list;
}
// move last (b) on top (a), alternation: splice or copyWithin
// ...L...H => ...HL... // move Hi from end to position Lo
function arrayShift(list, lo, hi)
{
if (hi<=lo || lo<0 || hi<0) {return;}
var tmp = list[hi]; cyclesAdd(hi - lo); movesAdd(hi - lo);
while (lo<hi)
{
list[hi--] = list[hi];
}
list[lo] = tmp;
return list;
}
// copy x values from src to dest array
function arrayCopy(src, i, i_end, dest, j, cmp)
{
while (i<i_end)
{dest[j++] = src[i++]; cyclesAdd(1); movesAdd(1);}
return dest;
}
// merge list1(a,b) with list1(c,d) to list2(e,f)
function arrayMerge(src, s1_start, s1_end, s2_start, s2_end, dest, d_start, cmp)
{
var i,j,k;
i = s1_start;
j = s2_start;
k = d_start;
while (i<s1_end && j<s2_end)
{
if (cmp(src[i], src[j]))
{dest[k++] = src[j++];}
else {dest[k++] = src[i++];}
cyclesAdd(1); movesAdd(1);
}
while (i<s1_end)
{dest[k++] = src[i++]; cyclesAdd(1); movesAdd(1);}
while (j<s2_end)
{dest[k++] = src[j++]; cyclesAdd(1); movesAdd(1);}
return dest;
}
Shuffle-sort (Nahodne zamichani pomoci sortu)
list.sort( function(a,b) { return 0.66 - Math.random(); } );
Multi-column-array-sort (serazovani pomoci vice sloupcu)
function isArray(item) {return typeof(item)=='object' && item!=null;}
function MultiSortClass(opt)
{
var root = this;
this.opt = {};
this.func = {};
this.func.cmpDate = function (a,b)
{
return (a[3]>b[3] ? 1 : (a[3]<b[3] ? -1 : 0));
}
this.func.cmpStrAsc = function (a,b)
{
return a.length>b.length && a>b ? 1 : (a==b ? 0 : -1);
}
this.func.cmpStrDesc = function (b,a)
{
return a.length>b.length && a>b ? 1 : (a==b ? 0 : -1);
}
this.func.cmpNumAsc = function (a,b)
{
return a>b ? 1 : (a==b ? 0 : -1);
}
this.func.cmpNumDesc = function (b,a)
{
return a>b ? 1 : (a==b ? 0 : -1);
}
this.cmp = function (a,b)
{
var out, i;
out = 0;
for (i in root.opt)
{
out = root.opt[i](a[i],b[i]);
if (out!=0)
{
return out;
}
}
return out;
}
this.func.cbUpper = function(match,content0,content1)
{
return content0.toUpperCase() + content1.toLowerCase();
}
this.setOpt = function (opt)
{
var row, i, i_end, func;
root.opt = {};
if (!(isExist(opt) && isArray(opt)))
{
return;
}
i_end = opt.length;
for (i=0;i<i_end;i++) // convert {col:2,cmp:'num',order:'asc'} => root.func.cmpNumAsc
{
row = opt[i];
row.cmp = row.cmp.replace(/^([a-z])([a-z]+)$/i,root.func.cbUpper);
row.order = row.order.replace(/^([a-z])([a-z]+)$/i,root.func.cbUpper);
func = 'cmp'+row.cmp+row.order;
if (isFunction(root.func[func]))
{
root.opt[row.col] = root.func[func];
}
}
}
this.setOpt(opt);
}
/*
var arr = [
['a', 1, 11],
['a', 0, 10],
['a', 1, 9],
['a', 0, 8],
]
var x;
x = new MultiSortClass([
{col:1,cmp:'num',order:'asc'},
{col:2,cmp:'num',order:'asc'}
]);
arr.sort(x.cmp)
str = '';
for (i=0;i<arr.length;i++)
{
str += arr[i].join(', ') + ' \n '
}
alert(str)
*/