堆排序法的比较和交换次数

Question

我们在C中实现了heapsort排序算法来对结构的数据进行排序。我需要显示已经进行的比较次数和交换次数，以便比较实际和理论复杂度。

为了计算迭代和交换，我有 2 个递增的变量。 问题是，如果我在适当的地方增加它们，因为结果是一样的。 ？ 我想有些东西不见了，因为在我的例子中，对于 90000 条记录，我得到比较：1312958 和交换：1312958.

我这里有一个简单的堆排序方法实现

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

更新

我更改了统计变量的地方，得到如下结果：2895916 comparisons and no swap: 1402958。考虑到堆排序的理论复杂度N * LogN，2895916远远超过了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

您没有正确计算比较：您必须分开测试以确定比较实际发生的时间。

这里是修改版：

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