Pyramid Sort (Heapsort, Heap Sort)

The pyramidal sorting method, invented by D. Williams, is an improvement in traditional tree sorting.

A pyramid ( heap ) is a binary tree such that

a [i] ≤ a [2i + 1];

a [i] ≤ a [2i + 2].

More details

a [0] is the minimum element of the pyramid.

The general idea of ​​pyramidal sorting is to first build a pyramid from the elements of the original array, and then sort the elements.

The execution of the algorithm is divided into two stages.

Stage 1 Construction of the pyramid. We determine the right side of the tree, starting from n / 2-1 (lower level of the tree). We take an element to the left of this part of the array and sift it through the pyramid along the path where its smaller elements are located, which simultaneously rise up; of the two possible paths, select the path through the smaller element.

For example, an array to sort

24, 31, 15, 20, 52, 6

Arrange the elements in the form of the original pyramid; element number of the right part (6 / 2-1) = 2 - this is element 15.


The result of sifting element 15 through the pyramid.


The next screened item is 1, equal to 31.


Then, element 0, equal to 24.


Of course, the resulting array is not yet ordered. However, the screening procedure is the basis for pyramidal sorting. As a result of sifting, the smallest element is at the top of the pyramid.

Stage 2 Sorting on the built pyramid. We take the last element of the array as the current one. We change the upper (smallest) element of the array and the current one in places. Sift the current element (it is now the top one) through the n-1 element pyramid. Then we take the penultimate element, etc.




We continue the process. As a result, the array will be sorted in descending order.

Implementing pyramidal sorting in C

one
2
3
four
5
6
7
8
9
10
eleven
12
13
fourteen
fifteen
16
17
eighteen
19
twenty
21
22
23
24
25
26
27
28
29th
thirty
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
fifty
51
52
53
54
55
56
57
58
59
60
61
62

#include <stdio.h>
#include <stdlib.h>
// Function "sifting" through the heap - heap formation
void siftDown ( int * numbers, int root, int bottom)
{
int maxChild; // maximum child index
int done = 0; // flag that the heap is formed
// Until we reached the last row
while ((root * 2 <= bottom) && (! done))
{
if (root * 2 == bottom) // if we are in the last row,
maxChild = root * 2; // remember the left child
// otherwise, remember the larger descendant of two
else if (numbers [root * 2]> numbers [root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
// if the vertex element is less than the maximum descendant
if (numbers [root] <numbers [maxChild])
{
int temp = numbers [root]; // swap them
numbers [root] = numbers [maxChild];
numbers [maxChild] = temp;
root = maxChild;
}
else // otherwise
done = 1; // pyramid formed
}
}
// Sort function on the heap
void heapSort ( int * numbers, int array_size)
{
// Form the bottom row of the pyramid
for ( int i = (array_size / 2) - 1; i> = 0; i--)
siftDown (numbers, i, array_size - 1);
// Sift through the pyramid the remaining elements
for ( int i = array_size - 1; i> = 1; i--)
{
int temp = numbers [0];
numbers [0] = numbers [i];
numbers [i] = temp;
siftDown (numbers, 0, i - 1);
}
}
int main ()
{
int a [10];
// Fill the array with random numbers
for ( int i = 0; i <10; i ++)
a [i] = rand ()% 20 - 10;
// Output array elements before sorting
for ( int i = 0; i <10; i ++)
printf ( "% d" , a [i]);
printf ( "\ n" );
heapSort (a, 10); // call the sort function
// Output array elements after sorting
for ( int i = 0; i <10; i ++)
printf ( "% d" , a [i]);
printf ( "\ n" );
getchar ();
return 0;
}

Execution result

Analysis of the pyramidal sorting algorithm

Despite some external complexity, pyramidal sorting is one of the most effective. The sorting algorithm is effective for large n . In the worst case, n · log 2 n steps are required that move the elements. The average number of movements is approximately equal

(n / 2) log 2 n ,

and deviations from this value are relatively small.

Advantages and disadvantages

Advantages

• Has a proven worst case estimate of O (n log n).
• Sorts in place, that is, it requires only O (1) additional memory (if the tree is organized as shown above).

disadvantages

• Unstable - to ensure stability, you need to expand the key.
• On almost sorted arrays, it works for as long as on chaotic data.
• At one step, you have to make random sampling along the entire length of the array - therefore, the algorithm does not work well with caching and swapping memory.
• The method requires “instant” direct access; does not work on linked lists and other serial memory structures.
• Not parallelized.
• Merge sorting at O ​​(n) memory consumption is faster (O (n log n). With a lower constant) and is not subject to degradation on failed data.
• Due to the complexity of the algorithm, the gain is obtained only at large n. On small n (up to several thousand) Shell sort is faster.

Application
The heap sorting algorithm is actively used in the Linux kernel.