I have implemented Heapsort in c++, it indeed sorts the array, but is giving me higher CPU times than expected. It is supposed to spend nlog(n) flops, and it is supposed to sort it faster than, at least, bubblesort and insertionsort.
Instead, it is giving me higher cpu times than both bubblesort and insertion sort. For example, for a random array of ints (size 100000), I have the following cpu times (in nanoSeconds):
This is the code itself:
#include <iostream>
#include <assert.h>
#include <fstream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
typedef vector<int> intv;
typedef vector<float> flov;
typedef vector<double> douv;
void max_heapify(intv& , int);
void build_max_heap(intv& v);
double hesorti(intv& v)
{
auto t0 =chrono::high_resolution_clock::now();
build_max_heap(v);
int x = 0;
int i = v.size() - 1;
while( i > x)
{
swap(v[i],v[x]);
++x;
--i;
}
auto t1 = chrono::high_resolution_clock::now();
double T = chrono::duration_cast<chrono::nanoseconds>(t1-t0).count();
return T;
}
void max_heapify(intv& v, int i)
{
int left = i + 1, right = i + 2;
int largest;
if( left <= v.size() && v[left] > v[i])
{
largest = left;
}
else
{
largest = i;
}
if( right <= v.size() && v[right] > v[largest])
{
largest = right;
}
if( largest != i)
{
swap(v[i], v[largest]);
max_heapify(v,largest);
}
}
void build_max_heap(intv& v)
{
for( int i = v.size() - 2; i >= 0; --i)
{
max_heapify(v, i);
}
}
There's definitely a problem with the implementation of heap sort.
Looking at hesorti, you can see that it is just reversing the elements of the vector after calling build_max_heap. So somehow build_max_heap isn't just making a heap, it's actually reverse sorting the whole array.
max_heapify already has an issue: in the standard array layout of a heap, the children of the node at array index i are not i+1 and i+2, but 2i+1 and 2i+2. It's being called from the back of the array forwards from build_max_heap. What does this do?
The first time it is called, on the last two elements (when i=n-2), it simply makes sure the larger comes before the smaller. What happens when it is called after that?
Let's do some mathematical induction. Suppose, for all j>i, after calling max_heapify with index j on an array where the numbers v[j+1] through v[n-1] are already in descending order, that the result is that the numbers v[j] through v[n-1] are sorted in descending order. (We've already seen this is true when i=n-2.)
If v[i] is greater or equal to v[i+1] (and therefore v[i+2] as well), no swaps will occur and when max_heapify returns, we know that the values at i through n-1 are in descending order. What happens in the other case?
Here, largest is set to i+1, and by our assumption, v[i+1] is greater than or equal to v[i+2] (and in fact all v[k] for k>i+1) already, so the test against the 'right' index (i+2) never succeeds. v[i] is swapped with v[i+1], making v[i] the largest of the numbers from v[i] through v[n-1], and then max_heapify is called on the elements from i+1 to the end. By our induction assumption, this will sort those elements in descending order, and so we know that now all the elements from v[i] to v[n-1] are in descending order.
Through the power of induction then, we've proved that build_max_heap will reverse sort the elements. The way it does it, is to percolate the elements in turn, working from the back, into their correct position in the reverse-sorted elements that come after it.
Does this look familiar? It's an insertion sort! Except it's sorting in reverse, so when hesorti is called, the sequence of swaps puts it in the correct order.
Insertion sort also has O(n^2) average behaviour, which is why you're getting similar numbers as for bubble sort. It's slower almost certainly because of the convoluted implementation of the insertion step.
TL;DR: Your heap sort is not faster because it isn't actually a heap sort, it's a backwards insert sort followed by an in-place ordering reversal.