归并掉期和比较 [英] Mergesort Swaps and Comparisons
问题描述
我目前工作的一个分析项目中，我观察在Java中实现时不同算法的行为。我得到了一些code，它实现从归并算法在网上，现在我需要10000随机生成的整数（1至100,000）的阵列上运行该code和记录有多少掉期进行了比较。
我不完全相信在这一点上，在code递增的数互换和比较的变量。什么的期望值是什么？由于最佳，最差和平均情况下归并都是n日志（n）的这是否意味着我应该期待万*为掉期和比较的总和？
（对数10,000基地2）约= 138000下面是code，我猜，当原数组被改变的交换只发生，比较我不太肯定：
无效归并（INT低，诠释高）
//一个[低：高]是一个全局数组进行排序。
//小（P）为真，如果只有一个元件到
// 分类。在这种情况下，列表已经排序。
{
如果（低速＆其中;高）{//如果有一个以上的元素
//划分峰值到子问题。
//查找哪里拆分集。
INT中期=（低+高）/ 2;
//解决的子问题。
归并（低，中）;
归并（MID + 1，高）;
//合并的解决方案。
合并（低，中，高）;
}
}
无效合并（INT低，诠释中期，诠释高）
//一个[低：高]是一个包含两个全局数组排序
//子集在[低：中]，并在[中等+ 1：高。目标
//就是这两套合并成居住一组
//在[低：高。 B〔〕是一个辅助全球阵列。
{
INT H =低，I =低，J =中等+ 1，K;
而（（H＆LT; =中）及及（J＆LT; =高））{
如果（一个[H] LT = A [J]）{B [I] = A [H]; ^ h ++; }
否则{B [I] = A [J]。 J ++; }我++;
}
如果（H＆GT; MID）的（K = j的; K＆LT; =高; k ++）{
B〔Ⅰ〕=一个[k]的;我++;
}
其他的（K = H，K＆LT; =中等; k ++）{
B〔Ⅰ〕=一个[k]的;我++;
}
对于（K =低; K＆LT; =高; k ++）一[K] = B [K]
}
我不完全相信在这一点上，在code递增的数互换和比较的变量。的
我建议你创建的helper方法用于交换和比较操作。这将使你的增量柜台code的好地方。
由于最佳，最差和平均情况下归并都是n日志（n）的这是否意味着我应该期待万的的总和（登录10000基地2）约= 138000掉期和比较？*
你可以期待的是，比较次数成正比的的n log（n）的的其中输入的大小的 N 的。
I'm currently working on an analysis project where I'm observing how different algorithms behave when implemented in Java. I got some code which implements a Mergesort algorithm from online, now I need to run this code on an array of 10,000 randomly generated integers (between 1 and 100,000) and record how many swaps and comparisons were made.
I'm not exactly sure at which point in the code to increment the variables that count Swaps and Comparisons. What would the expected value be? Since best, worst, and average case for Mergesort are all nlog(n) does this mean I should expect 10,000*(log base 2 of 10,000) approx = 138,000 for the sum of swaps and comparisons?
Here is the code, I'm guessing that a swap only happens when the original array is altered, comparisons I'm not too sure about:
void MergeSort(int low, int high)
// a[low : high] is a global array to be sorted.
// Small(P) is true if there is only one element to
// sort. In this case the list is already sorted.
{
if (low < high) { // If there are more than one element
// Divide P into subproblems.
// Find where to split the set.
int mid = (low + high)/2;
// Solve the subproblems.
MergeSort(low, mid);
MergeSort(mid + 1, high);
// Combine the solutions.
Merge(low, mid, high);
}
}
void Merge(int low, int mid, int high)
// a[low:high] is a global array containing two sorted
// subsets in a[low:mid] and in a[mid+1:high]. The goal
// is to merge these two sets into a single set residing
// in a[low:high]. b[] is an auxiliary global array.
{
int h = low, i = low, j = mid+1, k;
while ((h <= mid) && (j <= high)) {
if (a[h] <= a[j]) { b[i] = a[h]; h++; }
else { b[i] = a[j]; j++; } i++;
}
if (h > mid) for (k=j; k<=high; k++) {
b[i] = a[k]; i++;
}
else for (k=h; k<=mid; k++) {
b[i] = a[k]; i++;
}
for (k=low; k<=high; k++) a[k] = b[k];
}
I'm not exactly sure at which point in the code to increment the variables that count Swaps and Comparisons.
I suggest you create helper methods for the swap and the compare operation. That would give you good places for the increment-counter code.
Since best, worst, and average case for Mergesort are all nlog(n) does this mean I should expect 10,000(log base 2 of 10,000) approx = 138,000 for the sum of swaps and comparisons?*
What you can expect is that the number of comparisons is proportional to n log(n) where the size of the input is n.
这篇关于归并掉期和比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
