Count number of steps heap sort takes to sort an array

Question

so I have been playing around with implementing "famous" sorting algorithms to see how many steps they take to sort an array. However I am stuck on Heapsort, I can't figure out how to count the steps properly. With my implementation, sorting a 128 long array takes 630 steps on average - which is a lot more than nlog(n). When sorting the same array with quicksort, it is around 260-280 which is almost exactly nlogn, this tells me that the counter for heapsort is wrong. Here is my current code:

    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
    {
        int left = (index + 1) * 2 - 1;
        int right = (index + 1) * 2;
        int largest = 0;
        int stepCounter = steps;
        //For ascending sorting
        //Note: ideally there should be a maxHeapify for ascending and minHeapify for descending sorting seperately
        //however in this case it is easy to see what is happening
        if(asc)
        {
            if (left < size && heap[left] > heap[index])
            {
                largest = left;
            }
            else
            {
                largest = index;
            }

            if (right < size && heap[right] > heap[largest])
            {
                largest = right;
            }
        } else
        {//For descending sorting
            if (left < size && heap[left] < heap[index])
            {
                largest = left;
            }
            else
            {
                largest = index;
            }

            if (right < size && heap[right] < heap[largest])
            {
                largest = right;
            }
        }

        if (largest != index)
        {
            double temp = heap[index];
            heap[index] = heap[largest];
            heap[largest] = temp;
            stepCounter++;
            stepCounter = heapify(heap, size, largest, asc, stepCounter);
        }
        return stepCounter;
    }
    public static void heapSort(double[] heap, bool asc, int steps = 0)
    {
        int size = heap.Length;
        int i;
        int stepCounter = steps;
        //Build heap
        for (i = (size - 1) / 2; i >= 0; i--)
        {
            stepCounter = heapify(heap, size, i, asc, stepCounter);
        }

        for(i = heap.Length - 1; i > 0; i--)
        {
            double temp = heap[i];
            heap[i] = heap[0];
            heap[0] = temp;
            size--;
            stepCounter = heapify(heap, size, 0, asc, stepCounter);
        }
        Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
    }

Thanks. To be clear: I only want one statement at the end, printing the number of all steps, rather than lots of messages for 2-3 steps each.

edit: I changed around the code like so:

    public static int heapify(double[] heap, int size, int index, bool asc, int steps)
    {

        int stepCounter = 0;

        if (largest != index)
        {
            double temp = heap[index];
            heap[index] = heap[largest];
            heap[largest] = temp;
            stepCounter++;
            heapify(heap, size, largest, asc, stepCounter);
        }
        return stepCounter;
    }
    public static void heapSort(double[] heap, bool asc, int steps = 0)
    {
        int stepCounter = steps;
        //Build heap
        for (i = (size - 1) / 2; i >= 0; i--)
        {
            stepCounter += heapify(heap, size, i, asc, stepCounter);
        }

        for(i = heap.Length - 1; i > 0; i--)
        {
            double temp = heap[i];
            heap[i] = heap[0];
            heap[0] = temp;
            size--;
            stepCounter += heapify(heap, size, 0, asc, stepCounter);
        }
        Console.WriteLine("Heap sort has taken {0} steps", stepCounter);
    }

(deleted irrelevant bits). With this, I get 160-170 for 128 length arrays on average, and around 1300 steps for arrays of length ~1000. I think this sounds reasonable. Thank you @jdweng

Answer 1

However I am stuck on Heapsort, I can't figure out how to count the steps properly. With my implementation, sorting a 128 long array takes 630 steps on average - which is a lot more than nlog(n). When sorting the same array with quicksort, it is around 260-280 which is almost exactly nlogn, this tells me that the counter for heapsort is wrong.

This passage indicates that you do not understand big-O notation.

When we say that f(n) = O(g(n)) we mean that there exists a constant k and an N such that if N < n then |f(n)| < k |g(n)|. In other words, "the growth pattern is no worse than g(n)". It says nothing about the constant. And nothing about performance for small numbers.

Now heapsort and quicksort are both O(n log(n)). However they have different constants. Quicksort got its name because it is on average much faster than alternatives like mergesort and quicksort. The constant difference that you see reflects that.

But collect data on n for several values and graph f(n)/(n log(n)).