heapsort - implementation's complexity

Question

I wrote heapsort (Cormen). Algorithm is sorting correctly but complexity is greater than expected.

void heap_sort(int tab[], int length)
{
    build_max_heap(tab, length);
    int heap_size = length;
    for (int i = length-1; i > 1; i--)
    {
        int tmp = tab[1];
        tab[1] = tab[i];
        tab[i] = tmp;
        heap_size--;
        max_heapify(tab, 1, heap_size);
    }
}

void max_heapify (int tab[], int i, int length)
{
    int largest;
    int l = i * 2;
    int r = i * 2 + 1;
    if (l < length and tab[l] > tab[i])
        largest = l;
    else
        largest = i;
    if (r < length and tab[r] > tab[largest])
        largest = r;
    if (largest != i)
    {
        int tmp = tab[i];
        tab[i] = tab[largest];
        tab[largest] = tmp;
        max_heapify(tab, largest, length);
    }
}

void build_max_heap(int tab[], int length)
{
    for (int i = length/2; i >= 1; i--)
        max_heapify(tab, i, length);
}

For 15000000 numbers generated by rand() it lasted longer than sorting with Shell sort in this implementation:

void shell_sort (int tab[], int length)
{
    int x = 2;
    int q;
    do
    {
        x*=2;
        q=2*(length/x) + 1;
        for(int i = q, val, j; i < length; i++)
        {
            val = tab[i];
            for(j = i - q ; j >= 0 and tab[j] > val; j-=q)
            {
                tab[j + q] = tab[j];
            }
            tab[j + q] = val;
        }
    }while (q > 1);
}

Test:

HEAPSORT
Time for 1000000 elements: 0.336 s
Time for 2000000 elements: 0.732 s
Time for 3000000 elements: 1.142 s
Time for 4000000 elements: 1.595 s
Time for 5000000 elements: 2.034 s
Time for 6000000 elements: 2.513 s
Time for 7000000 elements: 3.023 s
Time for 8000000 elements: 3.51 s
Time for 9000000 elements: 4.02 s
Time for 10000000 elements: 4.558 s
Time for 11000000 elements: 5.095 s
Time for 12000000 elements: 5.595 s
Time for 13000000 elements: 6.183 s
Time for 14000000 elements: 6.7 s
Time for 15000000 elements: 7.367 s

SHELLSORT
Time for 1000000 elements: 0.343 s
Time for 2000000 elements: 0.779 s
Time for 3000000 elements: 1.182 s
Time for 4000000 elements: 1.654 s
Time for 5000000 elements: 2.218 s
Time for 6000000 elements: 2.672 s
Time for 7000000 elements: 3.34 s
Time for 8000000 elements: 3.778 s
Time for 9000000 elements: 4.297 s
Time for 10000000 elements: 4.903 s
Time for 11000000 elements: 4.872 s
Time for 12000000 elements: 5.514 s
Time for 13000000 elements: 6.29 s
Time for 14000000 elements: 6.994 s
Time for 15000000 elements: 7.121 s

I repeated the test many times. What's wrong with the algorythm?

Once the heap is made, to sort it: `while (first != last) { std::pop_heap(first, last--); }` — David, Mar 18 '16 at 21:49
Since it's being made for educational purposes I'm not allowed to use `std::pop_heap`. I should have mentioned that. — maksym, Mar 18 '16 at 21:54
Well, for organizational purposes I recommend keeping things simpler by writing `make_heap`, `sort_heap`, `push_heap`, and `pop_heap` functions separately, where `sort_heap` is just the 2 liner I wrote above. — David, Mar 18 '16 at 22:08
Are you assuming that the shell sort's average case performance is proportional to N^2? Just from the data you can see that's not true. — Paul Hankin, Mar 19 '16 at 00:50
@maksym - the example heap sort code fails to sort the first element in some cases. For example start with {7,3,6,2,5,0,1,4}, and it ends up with {7,0,1,2,3,4,5,6}. — rcgldr, Mar 19 '16 at 21:08
@maksym - true, the issue seems to be the performance of shell sort. Take a look at the [wiki article for shell sort](http://en.wikipedia.org/wiki/Shellsort) — rcgldr, Mar 21 '16 at 02:26

score 0 · Accepted Answer · answered Mar 19 '16 at 01:06

First note, big-O and raw performance have a complicated relationship. In the case of heapsort, poor memory locality will cause it to scale worse on computers than big-O would suggest. By contrast shell sort is only very slightly worse than O(n log(n)) and most of its passes have decent memory locality.

I'm therefore not surprised that they are comparable.

That said, you could try turning max_heapify from a recursive function into a loop. That may avoid a certain amount of stack manipulation.

heapsort - implementation's complexity

1 Answers1

Linked