Блог

Сортировка, похоже, работает правильно. По крайней мере, он сортируется правильно 🙂 Осталось только посчитать количество сравнений и свопов. Как его рассчитать и вывести?Как-то застопорился на этом этапе.. Я буду очень благодарен вам за помощь.Если вы продемонстрируете это с обновленным кодом , я буду вдвойне благодарен.

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

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

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

        if(2*head   2 < n amp;amp; 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;
}
 

подсчитайте количество сравнений и свопов

создание функций

 //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: %un", comparisons, swaps);
}