在合并排序C ++中使用合并时的随机值

亚历克斯

对于一个小的家庭作业,我应该编写一个简单的合并函数,其原型如下所示:

void merge(int a[], int left_low,  int left_high, int right_low, int right_high)

这些指示说,为简单起见,我们仅采用一个数组,a[]right_low = left_high + 1我们还将最终值存储在a[]传入的原始数组中。本质上,对于具有值的数组,a[] = {1,3,10,4,7,8}它看起来像这样:

a = {1, 3,     10 ,         4,    7,      8}
     ^         ^            ^             ^ 
  left_low  left_high    right_low     right_high

对于此作业,我们必须通过一些测试。第一个是两个数组之间的简单合并。第二个是老师自己的merge_sort函数,他在一些随机排序的数组上调用。这是我的实现merge()

void merge(int a[], int left_low,  int left_high,
                    int right_low, int right_high) {
    int temp[right_high + 1]; // temporary array to store the result
    int left_i = left_low, right_i = right_low, temp_i = 0;

    // while the temporary array is not filled
    while(temp_i != right_high + 1)
    {
        if(left_i == left_high + 1)
            temp[temp_i++] = a[right_i++];
        else if(right_i == right_high + 1)
            temp[temp_i++] = a[left_i++];
        else if(a[left_i] < a[right_i])
            temp[temp_i++] = a[left_i++];
        else
            temp[temp_i++] = a[right_i++];
    } // end while
    for(int i = 0; i < temp_i; ++i)
        a[i] = temp[i];
}

当他调用第一个测试时,他只检查两个数组的合并,我的函数起作用了,单个数组现在已排序。但是,当他调用他的merge_sort函数时,我最终得到了垃圾值。这是他的测试功能:

template<class T>
void print (std::string label, T a[], int length, bool report_sorted) {
  bool sorted = true;
  std::cout << label;
  for (int i=0; i<length; ++i) {
    std::cout << a[i];
    if (i == length-1)
      std::cout << std::endl;
    else {
      std::cout << ", ";
      if (a[i] > a[i+1])
        sorted = false;
    }
  }
  if (report_sorted)
    std::cout << (sorted ? "    Sorted" : "    Not Sorted") << std::endl;
}

void shuffle(int values[], int length) {
  std::vector<int> v_values;
  for (int i=0; i<length; ++i)
    v_values.push_back(values[i]);
  std::random_shuffle(v_values.begin(),v_values.end());
  for (int i=0; i<length; ++i)
    values[i] = v_values[i];
}

//Recursive Merge Sort
template<class T>
void merge_sort(T a[], int low, int high) {
  if (high - low < 1)               //Base case: 0 or 1 value to sort -> sorted
    return;
  else {
    int mid = (low + high)/2;       //Split in 1/2
    merge_sort(a, low, mid);        //Recursively sort low to mid
    merge_sort(a, mid+1, high);     //Recursively sort mid+1 to high
    merge(a, low,mid, mid+1,high);  //Merge sorted parts of array
  }
}

//Standard Merge Sort (calls a generalized one, with more parameters)
template<class T>
void merge_sort(T a[], int length) {
  merge_sort(a, 0, length-1);
}

std::cout << "\n\nTesting merge in merge sort" << std::endl;
    int test_merge_sort[10] = {1,2,3,4,5,6,7,8,9,10};
    for (int i=0; i<5; i++) {
      shuffle(test_merge_sort, 10);
      print("\n  Array before sort: ", test_merge_sort, 10, false);
      merge_sort(test_merge_sort, 10);
      print("  Array after  sort: ", test_merge_sort, 10, true);
    }

由于某种原因,我的输出最终看起来像这样:

 Array before sort: 3, 9, 2, 5, 8, 4, 6, 10, 1, 7
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: 1995111146, 1975317641, 4, 0, -944749486, 5443192, 5443196, 5439488, 4, -944749486
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: -944749486, -944749486, 5443196, 4, 5439488, 1995111146, 5443192, 1975317641, 0, 4
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: 1975317641, -944749486, 4, 4, 5439488, 5443192, 5443196, -944749486, 0, 1995111146
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: -944749486, 5443192, 5443196, 1975317641, 4, 0, -944749486, 5439488, 1995111146, 4
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

我的合并代码可能出什么问题了吗?

谢尔盖·卡里尼琴科(Sergey Kalinichenko)

问题是您输入的条目数计算temp错误:您的代码认为right_high + 1正确,但正确的公式是right_high - left_low + 1

例如,当一个调用为您提供索引10、15、16、26时,您的代码将尝试合并27个值,而应该只合并17个值(即索引10到26,包括两端)。

left_low为零时,这没有区别,因此您的测试用例运行良好。但是一旦left_low变为非零值(例如,当对数组的右半部分进行排序时),您的代码就会“超调”两个数组,将垃圾值放入tmp数组a中并在其中覆盖值

同样,最后一个for循环中的分配也需要偏移left_low

for(int i = 0; i < temp_i; ++i)
    a[i+left_low] = temp[i];

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档