how to count heapsort key comparisons [closed]

问题:

I wrote a little C# command application. Four arrays are supposed to be sorted with a heapsort algorithm. I took an algorithm from a website and its running just fine. Now I want to count the key-comparisons the algorithm needs to sort one array. I tried to count the comparisons via for loop but its seems to be wrong... Any ideas where I have to count for it?

Here's my sorting algorithm method. GlobalVar.CountVal is simply a public static int property.

public static void HeapSort(int[] array, int arr_ubound)
{
    int i, j;
    int lChild, rChild, pNode, root, temp;

    root = (arr_ubound - 1) / 2;

    for (j = root; j >= 0; j--)
    {
        for (i = root; i >= 0; i--)
        {
            GlobalVar.CountVal += 1;
            lChild = (2*i)+1;
            rChild = (2*i)+2;

            if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
            {
                if (array[rChild] >= array[lChild])
                    pNode = rChild;
                else
                    pNode = lChild;
            }
            else
            {
                if (rChild > arr_ubound)
                    pNode = lChild;
                else
                    pNode = rChild;
            }

            if (array[i] < array[pNode])
            {
                temp = array[i];
                array[i] = array[pNode];
                array[pNode] = temp;
            }
        }
    }

    temp = array[0];
    array[0] = array[arr_ubound];
    array[arr_ubound] = temp;
    return;
}

Here's the full code: http://pastebin.com/4Y0NQECP

回答1:

By using this comparer instead of the comparison operators (>= and <), you can count the comparisons properly.

public class CountingComparer<T> : Comparer<T>
{
    public int Count { get; private set; }
    IComparer<T> defaultComparer = Comparer<T>.Default;
    public override int Compare(T left, T right)
    {
        this.Count++;
        return defaultComparer.Compare(left, right);
    }
}

To use a comparer like this, here's how you modify your code:

x [op] y // becomes
comparer.Compare(x, y) [op] 0
// e.g.
if (array[rChild] >= array[lChild]) // becomes
if (comparer.Compare(array[rChild], array[lChild]) >= 0)

Then just make sure that you use this comparer for every comparison in the heapsort (but only in that one sorting). The full code (as I ran in LINQPad) is at http://pastebin.com/UXAQh9B3. I changed your method from hardcoded to generic to more easily identify where the comparer needed to be used.

The comparison counts for your data are as follows:

1 - 652
2 - 652
3 - 0
4 - 155