堆排序交换和比较。如何通过两个函数传递它们
Heapsort swap and comparisons. How to pass them through two functions
我正在尝试计算 C++ 中堆排序算法的交换和比较。到目前为止,我已经编写了主要函数和两个方法(都是堆排序算法)。
int main()
{
int countComp = 0, countSwap = 0;
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n, countComp, countSwap);
cout << "Sorted array is \n";
printArray(arr, n);
cout << "comparisons: " << countComp << " swaps: " << countSwap << endl;
}
我知道我犯了某种逻辑错误,因为通过参数传递变量然后用递归调用这些函数对我来说非常混乱。
void heapify(int arr[], int n, int i, int& countComparisons, int& countSwaps)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
{
countComparisons++;
largest = l;
}
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
{
countComparisons++;
largest = r;
}
// If largest is not root
if (largest != i)
{
countSwaps++;
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest, countComparisons, countSwaps);
}
}
// main function to do heap sort
void heapSort(int arr[], int n, int& countComparisons, int& countSwaps)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, countComparisons, countSwaps);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
countSwaps++;
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, n, 0, countComparisons, countSwaps);
}
}
我很确定错误与通过引用传递的参数有关。有人可以纠正我吗?我被这个问题困住了。或者也许有更好的方法来计算交换和比较?
如果我 运行 这个,我得到答案:
比较:12 互换:16
Sorted array is
13, 12, 11, 5, 7, 6,
comparisons: 12 swaps: 16
您在 heapSort
中有一个错误导致了错误的排序结果。它还会导致成功排序失败的比较和交换次数增加。在对 heapify
的第二次调用中将 n
更改为 i
void heapSort(int arr[], int n, int& countComparisons, int& countSwaps)
{
for(int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, countComparisons, countSwaps);
for(int i = n - 1; i >= 0; i--)
{
countSwaps++;
swap(arr[0], arr[i]);
//heapify(arr, n, 0, countComparisons, countSwaps);
heapify(arr, i, 0, countComparisons, countSwaps); //<=== changed `n` to `i`
}
}
结果:
Sorted array is
5, 6, 7, 11, 12, 13,
comparisons: 7 swaps: 11
我正在尝试计算 C++ 中堆排序算法的交换和比较。到目前为止,我已经编写了主要函数和两个方法(都是堆排序算法)。
int main()
{
int countComp = 0, countSwap = 0;
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n, countComp, countSwap);
cout << "Sorted array is \n";
printArray(arr, n);
cout << "comparisons: " << countComp << " swaps: " << countSwap << endl;
}
我知道我犯了某种逻辑错误,因为通过参数传递变量然后用递归调用这些函数对我来说非常混乱。
void heapify(int arr[], int n, int i, int& countComparisons, int& countSwaps)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
{
countComparisons++;
largest = l;
}
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
{
countComparisons++;
largest = r;
}
// If largest is not root
if (largest != i)
{
countSwaps++;
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest, countComparisons, countSwaps);
}
}
// main function to do heap sort
void heapSort(int arr[], int n, int& countComparisons, int& countSwaps)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, countComparisons, countSwaps);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
countSwaps++;
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, n, 0, countComparisons, countSwaps);
}
}
我很确定错误与通过引用传递的参数有关。有人可以纠正我吗?我被这个问题困住了。或者也许有更好的方法来计算交换和比较?
如果我 运行 这个,我得到答案: 比较:12 互换:16
Sorted array is 13, 12, 11, 5, 7, 6, comparisons: 12 swaps: 16
您在 heapSort
中有一个错误导致了错误的排序结果。它还会导致成功排序失败的比较和交换次数增加。在对 heapify
n
更改为 i
void heapSort(int arr[], int n, int& countComparisons, int& countSwaps)
{
for(int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, countComparisons, countSwaps);
for(int i = n - 1; i >= 0; i--)
{
countSwaps++;
swap(arr[0], arr[i]);
//heapify(arr, n, 0, countComparisons, countSwaps);
heapify(arr, i, 0, countComparisons, countSwaps); //<=== changed `n` to `i`
}
}
结果:
Sorted array is 5, 6, 7, 11, 12, 13, comparisons: 7 swaps: 11