== Description ==

'''PyramidSelectionSort''' 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.

{{Aligned table
|cols=2|class=wikitable
|col1header=on
|col1align=left
| Category | Sorting algorithm
| Sub category | Selection sort
| Name | '''PyramidSelectionSort'''
| Data structure | Array
| Comparations | <math>O(n\log n)</math>
| Timing | <math>O(n\log n)</math>
| Spacing | <math>2*n + n</math> (input + output + index table)
| Stability | Stable algorithm
}}

== Statistics from real code execution (average) ==

<pre>
n         = 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
</pre>

== Schematic of work ==

<pre style="overflow:auto; width:auto;">
pavel 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
</pre>

== Code (javascript) ==
<syntaxhighlight lang="JavaScript">
<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>
</syntaxhighlight>

== References ==
{{reflist}}

== Links ==

=== Internal links ===

* [[Data Structures and Algorithms/Sorting Data]]

=== External links ===

* [[wikipedia:Tournament_sort|Selection Tournament_sort]]
* [https://mlich.zam.slu.cz/js-sort/sorting4-pokus.htm Test of sorting algorithms], generate statics (javascript)