Data Structures and Algorithms/PyramidSelectionSort
Description
editPyramidSelectionSort get first pair of values, compare it and save minimal value (index) to new array. Repeat for all pair, create row 0. Repeat for row 0, create row 1... Find minimal value. Create tournament table of winners. Then remove minimal and rebuild pyramid branch (where minimal figured) and again find minimal value.
| Category | Sorting algorithm |
|---|---|
| Sub category | Selection sort |
| Name | PyramidSelectionSort |
| Data structure | Array |
| Comparations | |
| Timing | |
| Spacing | (input + output + index table) |
| Stability | Stable algorithm |
Statistics from real code execution (average)
editn = 1.024 value-min = 0 value-max = n/2 // 50% of array contain some repeating value ------------------ compares ~ 8.886 (Tim-sort ~8.961, Select-sort ~523.776) cycles ~ 11.262 (Tim-sort ~16.097) moves ~ 1.798 (Tim-sort ~13.659, Select-sort ~3.054) stability = stable
Schematic of work
editpavel vs. tomas zdenek vs. michal
| | | |
+----+----+ +----+----+
| |
tomas zdenek
| |
+---------+---------+
|
zdenek --- out: zdenek
pavel vs. tomas - michal --- remove winner and find new winner in this branch
| | | |
+----+----+ +----+----+
| |
tomas michal
| |
+---------+---------+
|
tomas --- out: zdenek, tomas
pavel - - michal
| | | |
+----+----+ +----+----+
| |
pavel michal
| |
+---------+---------+
|
pavel --- out: zdenek, tomas, pavel, michal
3 1 2 2 0 3 1 0 // input
3-1 2-2 0-3 1-0 // compare pair from input and create row 0 of minimal
1-2 0-----0 // row 0, pyramid of minimal values / index of position (for scheme i use value, use position in alg. code)
1-----0 . . // row 1
0 . . // row 2, save minimal to out "0", cmp = 7
. .
1 2 3---0 // rebuild branch (row[0][4,5,6,7], row[1][3,4], row[2][1]) and compare new winner in branch
1-----------0
. 0 // save "0", cmp + 2
. x
1 2 3-1 x // rebuild branch
1---------1
1 // save "1", cmp + 2
x
3---2 3 1 // rebuild branch
2-------1
1 // save "1", cmp + 2
x
3 2 3 x // rebuild branch (when not even or odd value from input, use "x" (-1 in alg. code), when "x" copy second index to next level)
2-----3
2 // save "2", cmp + 1
x
3-----2 3 // rebuild branch (when "x", copy index to next level)
2---3
2 // save "2", cmp + 2
x
3 x 3 // rebuild branch (when "x", copy index to next level)
3---------3
3 // save "3", cmp + 1
3 // save last "3"
===============
0 0 1 1 2 2 3 3 // output, suma(cmp) = 7+2+2+2+1+2+1 = 17
Code (javascript)
edit<div></div>
<script>
// Created by Peter Mlich (2022)
// build first pyramid of minimal values
function pyramid_part1_buildPyramid(list, cmp, i_start, i_end, size)
{
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)
{
glob.cycles++;
if (cmp(list[i], list[j])>0)
{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])>0)
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = list[i-2];
list[i-2] = tmp;
glob.moves += 4;
pyramid[lvl][k] = i;
}
else {if (cmp(list[i-1], list[i])>0)
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = tmp;
glob.moves += 3;
}}
}
i_end = k;
lvlp1 = lvl + 1;
while (i_end>1)
{
glob.cycles++;
pyramid[lvlp1] = [];
k = 0;
i = 0;
j = 1; // =i+1
while (j<i_end)
{
glob.cycles++;
if (cmp(list[ pyramid[lvl][i] ], list[ pyramid[lvl][j] ])>0)
{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++)
{
glob.cycles++;
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])>0)
{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])>0)
{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];
glob.moves += 2;
// je sude, pak vymen za liche a 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 vsechna nutna 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 vsechna nutna porovnani
val2 = empty;
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_end; lvl++)
{
glob.cycles++;
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])>0)
{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])>0)
{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(cmp, start, end, n)
{
if (o.size<2) {return o.n;}
var pyramid_data, i, x, y, endm3 = o.end-3;
x = o.n;
y = o.n==1 ? 2 : 1;
pyramid_data = pyramid_part1_buildPyramid(arr[x], o.fn_cmp, o.start, o.end, o.size); // create pyramid of index from minimal values of pair
i = o.start;
arr[y][i] = arr[x][pyramid_data[2]];
glob.moves++;
i++;
while (i<o.end)
{
glob.cycles++;
pyramid_data = pyramid_part2_rebuildPyramid(pyramid_data[0], pyramid_data[1], pyramid_data[3], arr[x], o.fn_cmp, o.end, endm3)
arr[y][i] = arr[x][pyramid_data[2]];
glob.moves++;
i++;
}
return y;
}
// note: code is optimalized for my tester
function sortCompare (a, b)
{
glob.cmps++;
var c = a - b;
return c>0 ? 1 : (c<0 ? -1 : 0);
};
function swap (list, a, b)
{
if (a==b) {return;}
var tmp = list[a];
list[a] = list[b];
list[b] = tmp;
glob.moves += 3;
};
var arr = [null, [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4], [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]]
var glob = {moves: 0, cycles: 0, cmps: 0};
var o = {start: 0, end: 16, size: 16 - 0, n: 1, moves: 0, cycles: 0, fn_cmp: sortCompare};
var log = [], i=0, n;
log[i++] = 'array-before ' + JSON.stringify(arr[1])
o.n = PyramidSelectSort(o.fn_cmp, o.start, o.end, o.n);
log[i++] = 'array-after ' + JSON.stringify(arr[o.n])
log[i++] = 'glob ' + JSON.stringify(glob)
log[i++] = 'n ' + JSON.stringify(o.end - o.start)
document.getElementsByTagName('DIV')[0].innerHTML = log.join('<br>')
/*
array-before [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4]
array-after [0,0,1,2,2,3,4,4,4,6,6,7,7,7,7,7]
glob {"moves":22,"cycles":78,"cmps":47}
n 16
*/
</script>