C++マージソートの問題

Question

私はC++を初めて使用していて、マージソートのコードを開発しようとしていました。私はサイズ15のサンプル配列でそれをテストしましたが、コードによって出される答えは正しくありません。私は何がうまくいかないのか理解できません。ここに私のコードは次のとおりです。

#include <stdlib.h> 
#include <stdio.h> 
#include <iostream> 
#include <string> 
#include <fstream> 
#include <vector> 
#include <unistd.h> 
#include <cstdlib> 

using namespace std; 

//two arrays, input 
int initial[15] = {200,1,2,9,8,98,6,44,5,4,67,15,3,2,0}; 
//for output 
int fin[15]; 

void sort(int* ini, int left, int right, int m); 

//saperate the input in a recursion 
void devide(int* ini, int left, int right){ 
    int m; 

    if(left < right){ 
      m = (left + right)/2; 
      devide(ini, left, m); 
      devide(ini, m+1, right); 

      sort(ini, left, right, m); 
    } 
} 


//sorting 
void sort(int* ini, int left, int right, int m){ 

    //first half, start at the first element in the input array 
    int first_h = left; 

    //second half, start at the first element after the 
    // middle element in the input array 
    int second_h = m+1; 

    //index for output array 
    int out = left; 

    //comparing, if both half of array have element 
    while(first_h <= m && second_h <= right){ 

      //put the smaller in the the output array 
      if(initial[first_h] < initial[second_h]){ 
       fin[out] = initial[first_h]; 
       first_h++; 
      } 
      else{ 
       fin[out] = initial[second_h]; 
       second_h++; 

      } 
      out++; 
    } 

    //if one of half of input is empty, put the rest element into the 
    // output array 
    while(first_h <= m){ 
      fin[out] = initial[first_h]; 
      out++; 
     first_h++; 
    } 
    while(second_h <= right){ 
      fin[out] = initial[second_h]; 
      out++; 
      second_h++; 
    } 
} 

int main(){ 
    devide(initial, 0, 14); 

    for(int i =0; i<15; i++){ 
      cout<<fin[i]; 
      cout<<","; 
    } 
    return 0; 
} 

開始の出力は[]、[]フィンであるされています。だから、あなたは考慮していない一つの小さなミスが、あなたは、ということです

5,4,67,15,3,2,0,200,1,2,9,8,98,6,44, 

Answer 1

ポインタ配列iniを渡しますが、まだメソッドの初期値を使用していますが、もう1つの方法は、ソートされた値をini配列に代入する一時配列を取ることです。

だからあなたのコードは、これは、より良いアルゴリズムを理解するのに役立ちます。この

void sort(int* ini, int left, int right, int m){ 
    int first_h = left; 
    int second_h = m+1; 
    int out = left; 
    while(first_h <= m && second_h <= right){ 
      if(ini[first_h] < ini[second_h]){ 
       fin[out] = ini[first_h]; 
       first_h++; 
      } 
      else{ 
       fin[out] = ini[second_h]; 
       second_h++; 

      } 
      out++; 
    } 

    while(first_h <= m){ 
      fin[out] = ini[first_h]; 
      out++; 
     first_h++; 
    } 
    while(second_h <= right){ 
      fin[out] = ini[second_h]; 
      out++; 
      second_h++; 
    } 
    for(int i=left; i<out; i++) 
    { 
     ini[i] = fin[i]; 
    } 
} 

希望のようなものになるはずです！