C++でマージソートを実装できません

Question

私はアルゴリズムに慣れていません。マージソートの作業をしようとしていますが、正しい出力が得られません。コンパイルエラーはありませんが、ソートされた配列として出力にランダムな値が表示され、どこかに欠陥があると思います。あなたのmerge機能で

void merge_sort(int[], int, int); 
void merge(int[], int, int, int); 
void printarray(int[], int); 

int main() { 
    int Arr[100], num_of_elements; 
    cout << "Enter the number of elements (max 100): "; 
    cin >> num_of_elements; 
    cout << "Enter array elements: \n"; 
    for (int i = 0;i < num_of_elements;++i) 
     cin >> Arr[i]; 
    merge_sort(Arr, 0, num_of_elements - 1); 
    cout << "\nAfter Sorting (by Merge Sort):\n"; 
    printarray(Arr, num_of_elements); 
    cout << endl; 
    return 0; 
} 

void merge_sort(int arr[], int left, int right) { 
    if (left < right) { 
     int mid = (left + right)/2; 
     merge_sort(arr, left, mid); 
     merge_sort(arr, mid + 1, right); 
     merge(arr, left, mid, right); 
    } 
} 

void merge(int arr[], int left, int mid, int right) { 
    int i, j, k; 

    /* Calculate the lengths of the subarrays and copy the elements into them */ 
    int lenght_left = mid - left + 1; 
    int length_right = right - mid; 
    int *leftarray = new int[lenght_left]; 
    int *rightarray = new int[length_right]; 
    for (i = 0;i < lenght_left;++i) 
     leftarray[i] = arr[left + i]; 
    for (j = 0;j < length_right;++j) 
     rightarray[j] = arr[mid + 1 + j]; 

    /* Reordering the elements in the original array */ 
    for (k = left, i = 0, j = 0;k <= right;++k) { 
     if (leftarray[i] <= rightarray[j]) 
      arr[k] = leftarray[i++]; 
     else 
      arr[k] = rightarray[j++]; 
    } 

    /* Copy remaining elements into the array */ 
    while (i < lenght_left) 
     arr[k] = leftarray[i++]; 
    while (j < length_right) 
     arr[k] = rightarray[j++]; 
    delete[](leftarray); 
    delete[](rightarray); 
} 

void printarray(int arr[], int num) { 
    cout << "Displaying Elements in array: \n"; 
    for (int i = 0;i < num;i++) 
     cout << arr[i] << " "; 
} 

Answer 1

：あなたはループを制御するために使用している条件が適切ではない

/* Reordering the elements in the original array */ 
for (k = left, i = 0, j = 0; k <= right; ++k) { 
//       ^^^^^^^^^^^ 
// It should be i < lenght_left && j < length_right 
    if (leftarray[i] <= rightarray[j]) 
     arr[k] = leftarray[i++]; 
    else 
     arr[k] = rightarray[j++]; 
} 

、条件があなたのleftarrayとrightarrayに関してである必要があり、それがあるべき、といういずれかの配列が最後まで到達したら、条件をi < lenght_left && j < length_rightに変更します。

と同じ機能で、残りの要素をコピーするとき：

/* Copy remaining elements into the array */ 
while (i < lenght_left) 
    arr[k] = leftarray[i++]; 
//  ^^^ 
while (j < length_right) 
    arr[k] = rightarray[j++]; 
//  ^^^ 

をここで、あなたは、kをインクリメントk++にそれらを変更するのを忘れました。

Answer 2

ミスのカップルは、あなたが作っているがあります。

1. をあなたが

   すなわち代わりにマージしているときに、配列の長さにわたって行っていないことを確認する必要があります。

   を

   for (k = left, i = 0, j = 0;k <= right;++k) 
   

   あなたは持っている必要があります。

   for (k = left, i = 0, j = 0;k <= right && i <lenght_left && j<length_right;++k) 
   

2. 残っている要素を追加するときは、配列カウンタを大きくすることを忘れないでください。 すなわち：

   while (i < lenght_left) 
       arr[k] = leftarray[i++]; 
   while (j < length_right) 
       arr[k] = rightarray[j++]; 
   

   あなたは持っている必要があります。

   while (i < lenght_left) 
       arr[k++] = leftarray[i++]; 
   while (j < length_right) 
       arr[k++] = rightarray[j++];