C.Heapsort .计算交换和比较的次数

Question

排序似乎工作正常。至少它排序正确 :) 它仍然只是计算比较和交换的次数。如何计算和输出它？在这一点上不知何故停滞不前。我将非常感谢你help.If你用更新的代码演示它，我将加倍感激。

#include <stdio.h>
#include <stdlib.h>

void keyDown(int* arr, int n, int head)
{
    int j;
    if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
    {
        j = 2*head + 2; 
    }
    else j = 2*head + 1;

    while(arr[head] < arr[j] && head < n / 2)
    {
        int tmp = arr[head];
        arr[head] = arr[j];
        arr[j] = tmp;
    
        head = j;

        if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
        {
            j = 2*head + 2; 
        }
        else j = 2*head + 1;
    }

}
void heapSort(int* arr, int n)
{  
    int i;
    for(i = n/2 - 1; i >= 0; i--)
    {
        keyDown(arr,n,i);
    }
    int l = n;
    while(l > 1)
    {  
        l--;
        
        int tmp = arr[l];
        arr[l] = arr[0];
        arr[0] = tmp;
        
        keyDown(arr,l,0);
    }
}
int main(int argc, char *argv[]) {
    int n=10;
    int start, end,i;
    int *arr;
        arr=(int *)malloc(n*sizeof(int));
        time_t invocation_time = time(NULL);
        srand(invocation_time);
        int s;
        for (s=0;s<n;s++)
        {
            arr[s] = rand() % 50;
            printf ("%d \n", arr[s]);
        }
        printf ("\n");  
        heapSort(arr, n);
        for (i=0;i<n;i++){
            printf ("%d \n", arr[i]);   
        }
    return 0;
}

Answer 1

count the number of comparisons and swaps

创建函数

//global counters
unsigned comparisons = 0, swaps = 0;

int lessthan(int a, int b) {
    comparisons++;
    return (a < b);
}
void swap(int *a, int *b) {
    swaps++;
    int tmp = *a; *a = *b; *b = tmp;
}

然后用您需要的特定函数替换现有代码中的比较和交换。

int main(int argc, char **argc) {
    //...
    if (lessthan(a[i], a[j])) swap(a+i, a+j);
    //...
    printf("comparisons: %u; swaps: %u\n", comparisons, swaps);
}

C.Heapsort .计算交换和比较的次数

C.Heapsort .Count the number of swaps and comparisons

c

sorting

heap

swap

heapsort