Number of comparisons and swaps of the heap sorting method

Question

We have implemented in C the heapsort sorting algorithm to sort the data of a structure.. I need to display the number of comparisons that have been made and the number of interchanges, in order to compare the practical and theoretical complexity.

To count iterations and interchanges, I have 2 variables that I increment. The question is, if I increment them where appropriate, because the result is the same. ? I guess something's missing because, in my case, for a number of 90000 records, I get comparisons: 1312958 and swaps: 1312958.

I have here a trivial implementation of the heap sort method

void heapify(Game *game, int n, int i, size_t *compCounter, size_t *swapCounter) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && game[left].id > game[largest].id) {
        largest = left;
    }
    if (right < n && game[right].id > game[largest].id) {
        largest = right;
    }
    if (largest != i) {
        (*compCounter)++;
        (*swapCounter)++;
        swap(&game[i], &game[largest]);
        heapify(game, n, largest, compCounter, swapCounter);
    }
}

Game *heapSort(Game *game, int n, size_t *compCounter, size_t *swapCounter) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(game, n, i, compCounter, swapCounter);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(&game[0], &game[i]);
        heapify(game, i, 0, compCounter, swapCounter);
    }
    return game;
}

UPDATE

I changed the place where the variables are counted, obtaining the following results: 2895916 comparisons and no swaps: 1402958. Considering that heap sort has the theoretical complexity N * LogN, 2895916 far exceeds the number 90000 * log (90000)

void heapify(Game *game, size_t n, size_t i, size_t *compCounter, size_t *swapCounter) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && game[left].id > game[largest].id) {
        largest = left;
    }
    *compCounter += 1;
    if (right < n && game[right].id > game[largest].id) {
        largest = right;
    }
    *compCounter += 1;
    if (largest != i) {
        swap(&game[i], &game[largest]);
        *swapCounter += 1;
        heapify(game, n, largest, compCounter, swapCounter);
    }
}

Game *heapSort(Game *game, size_t n, size_t *compCounter, size_t *swapCounter) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(game, n, i, compCounter, swapCounter);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(&game[0], &game[i]);
        *swapCounter += 1;
        heapify(game, i, 0, compCounter, swapCounter);
    }
    return game;
}

int main(){

size_t heapComp = 0, heapSwap = 0;
 heapSort(games5, n, &heapComp, &heapSwap);
   
    printf("Comps: %zu si nr swaps: %zu\n", heapComp, heapSwap);
}

Answer 1

Your are not counting the comparisons properly: you must separate the tests to identify when the comparisons actually occur.

Here is a modified version:

void heapify(Game *game, int n, int i, size_t *compCounter, size_t *swapCounter) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n) {
        (*compCounter)++;
        if (game[left].id > game[largest].id) {
            largest = left;
        }
    }
    if (right < n) {
        (*compCounter)++;
        if (game[right].id > game[largest].id) {
            largest = right;
        }
    }
    if (largest != i) {
        (*swapCounter)++;
        swap(&game[i], &game[largest]);
        heapify(game, n, largest, compCounter, swapCounter);
    }
}