什么是错在此实现合并排序？ [英] What is wrong in this implementation of merge sort?

问题描述

我知道有合并排序很多实现，但这是我曾经读过的书算法导论。下面code是排序合并的是无法正常工作的实现：

I know that there are many implementations of merge sort but this is one which I have read in the book "Introduction to algorithms". The following code is an implementation of merge sort which is not working correctly:

#include <iostream>

using namespace std;
void merge(int*a, int p, int q, int r) {  //function to merge two arrays

  int n1 = (q - p);  // size of first sub array

  int n2 = (r - q);  // size of second subarray

  int c[n1], d[n2];

  for (int i = 0; i <= n1; i++) {
    c[i] = a[p + i];
  }

  for (int j = 0; j <= n2; j++) {
    d[j] = a[q + j];
  }

  int i = 0, j = 0;

  for (int k = p; k < r; k++) {  // merging two arrays in ascending order

    if (c[i] <= d[j]) {
      a[k++] = c[i++];

    } else {
      a[k++] = d[j++];

    }
  }
}

void merge_sort(int*a, int s, int e) {
  if (s < e) {
    int mid = (s + e) / 2;
    merge_sort(a, s, mid);
    merge_sort(a, mid + 1, e);
    merge(a, s, mid, e);
  }
}

int main() {
  int a[7] { 10, 2, 6, 8, 9, 10, 15 };
  merge_sort(a, 0, 6);
  for (auto i : a)
    cout << i << endl;
}

这code不能正常工作。什么是错在这code？怎样才可以解决吗？

This code is not working correctly. What's wrong in this code? How can it be fixed?

推荐答案

有几件事情在你的逻辑实现了偏差。我已经表明他们明确如下：

There are couple of things gone wrong in the implementation of your logic. I have indicated them clearly below:

void merge(int*a,int p,int q,int r){  //function to merge two arrays

int n1= (q-p); // size of first sub array
int n2= (r-q); // size of second subarray
int c[n1+1],d[n2]; //you need to add 1 otherwise you will lose out elements

for(int i=0;i<=n1;i++){
    c[i]=a[p+i];
    }

for(int j=0;j<n2;j++){
    d[j]=a[q+j+1];//This is to ensure that the second array starts after the mid element
    }

    int i=0,j=0;
int k;
for( k=p;k<=r;k++){ // merging two arrays in ascending order
    if( i<=n1 && j<n2 ){//you need to check the bounds else may get unexpected results
        if( c[i] <= d[j] )
            a[k] = c[i++];
        else
            a[k] = d[j++];
    }else if( i<=n1 ){
        a[k] = c[i++];
    }else{
        a[k] = d[j++];
    }
}
}

这篇关于什么是错在此实现合并排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！