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);
}
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);
}
}