Pyramid selection sort

---

Description

Pyramid selection sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n\log n)$
Best-case performance	$O(n\log n)$
Average performance	$O(n\log n)$, 8.716 for n=1.000
Worst-case space complexity	$O(2)$ + index(n)

How it works? Pyramid selection sort creates a pyramid of minimal values from pairs. Repeat for the first level of minimums... After completion, remove the minimum and rebuild the pyramid branch.

Properties: The algorithm needs extra memory. It is fast. It is stable.

Statistics (average)

n         = 1.000
value-min = 0
value-max = n/2     // 50% of array contain some repeating value
------------------
compares  ~ 8.716   (Tim-sort ~8.680)
cycles    ~ 11.506  (Tim-sort ~20.969)
moves     ~ 1.753   (Tim-sort ~15.534, Select-sort ~2.979)
stability = stable

Schematic of work

3 1 2 2 0 3 1 0    // input

3-1 2-2 0-3 1-0    // compare pair from input and create level 1 of minimal
  1-2   0-----0    // new level 1 pyramid of index (for code i use index, for scheme i use value)
  1-----0          // new level 2
        0          // new level 3, cmp = 7

  1 2     3---0    // rebuild pyramid branch (select second value from input)
  1-----------0
              0    // save "0", cmp + 2

  1 2     3-1      // rebuild pyramid branch
  1---------1
  1                // save "1", cmp + 2

3---2     3 1      // rebuild pyramid branch
    2-------1
            1      // save "1", cmp + 2

3   2     3 x      // rebuild pyramid branch (when not even or odd value from input, use "x" (or -1), when "x" copy second index to next level)
    2-----3
    2              // save "2", cmp + 1

3-----2   3 x      // rebuild pyramid branch (when -1, copy index to next level)
      2---3
      2            // save "2", cmp + 2

3     x   3 x      // rebuild pyramid (when -1, 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+1+2+2+1 = 17

Code (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;
	}



// code 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>

Links

• [1] Selection sort

External links

• Test of sorting algorithms, generate statics (javascript)

This article "Pyramid selection sort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Pyramid selection sort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Monotonic Sort
• Twin sort algorithm
• Sorted list merging sort
• JSort
• Ordicate
• Binary priority list
• Stalin sort

---