Heapsort is one of the fastest sorting algorithms. The best and the worst cases for heapsort have same $O(n\log(n))$ performance.
At first heapsort creates heap from data with buildHeap function. Heap is organized in linear array as follows. Every $i$-th element has two children: $(2i)$-th element and $(2i+1)$-th one. The biggest element of the array is placed on the top of the heap.
After heap building top element is swapped with the latest in the array, then heap is rebuilt for the array with size decreased by one. These operations repeat till array size is bigger than one. Note that array indexes have to start from one for this implementation to work correctly (that is why I use size+1 for array size).
My implementation of heapsort is presented below. heapsort.cpp:
#include <iostream>
#include <cstdlib>
#include <algorithm>
template <typename T>
void checkRootNode(T *array, size_t root, size_t size) {
size_t left = 2*root;
size_t right = 2*root + 1;
if (left < size && array[root] < array[left]) {
std::swap(array[root], array[left]);
checkRootNode(array, left, size);
}
if (right < size && array[root] < array[right]) {
std::swap(array[root], array[right]);
checkRootNode(array, right, size);
}
}
template <typename T>
void buildHeap(T *array, size_t size) {
for (size_t i=size/2; i>0; --i) {
checkRootNode(array, i, size);
}
}
template <typename T>
void heapSort(T *array, size_t size) {
while (size > 1) {
std::swap(array[1], array[size-1]);
checkRootNode(array, 1, --size);
}
}
template <typename T>
void printArray(T *array, size_t size) {
for (size_t i=1; i < size; ++i) {
std::cout << array[i] << ' ';
}
std::cout << std::endl;
}
int main(void) {
size_t size = 23;
int *array = new int[size+1];
for (int i=1; i<size+1; ++i) {
array[i] = (100.0*rand())/RAND_MAX;
}
printArray(array, size);
buildHeap(array, size);
heapSort(array, size);
printArray(array, size);
delete [] array;
return 0;
}
Results:
[kenarius@cudasus]$ g++ heapsort.cpp
[kenarius@cudasus]$ ./a.out
84 39 78 79 91 19 33 76 27 55 47 62 36 51 95 91 63 71 14 60 1 24
1 14 19 24 27 33 36 39 47 51 55 60 62 63 71 76 78 79 84 91 91 95