C＋＋ マージソート

Question

C＋＋でテキストファイルに入力した整数をマージソートで昇順に羅列するプログラムを作成したいのですが、今のままではソートされずに入力した整数がそのまま表示されます。

#include <iostream>
#include <vector>

using namespace std ;
typedef vector<int> ARRAY ;

static void merge_sort(ARRAY & data, int i, int j){
  if (i>=j) return;
  int k = i;
  int mid = (i+j)/2;
  int n = mid + 1;

  merge_sort(data, i, mid);
  merge_sort(data, n, j);

  ARRAY temp;
  for(;;){
    if(data[i] <= data[n]){
      temp.push_back(data[i]);
      i++ ;
      if(i>mid){
	for(;n<=j;n++) temp.push_back(data[n]);
	break ;
      }
    }else{
      temp.push_back(data[n]);
      n++;
      if(n>j){
	for(;i<=mid; i++) temp.push_back(data[i]);
	break;
      }
    }
  }
}
int main (){
  ARRAY data ;
  int i ;
  while(cin >> i) data.push_back(i) ;
  int n = data.size() ;
  merge_sort(data,0,n-1) ;
  for( auto i : data) cout << i << endl ;
  return 0 ;
}

Comments

[y_waiwai]

このままではコードが読みづらいので、質問を編集し、</>(コードの挿入)ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

Answer 1

マージ結果を temp に入れただけで、data にはコピーしていませんね。
for (i = 0; k <= j; k++) data[k] = temp[i++]; を追加してみてください。

Answer 2

最後の出力の部分のコードが分かりません。

for( auto i : data) cout << i << endl ;
範囲for(range-based for)構文がわからんのでしょうか。

for( auto i : data) // data内の各要素iに対し (i の型はコンパイラの推論に従う)
cout << i << endl ; // i をプリントする。

Comments

[syachi]

回答ありがとうございます。
今のコードだとソートされずに入力した整数がそのまま表示されるのですがどこを変えるべきなのか分かりません。

[episteme]

関数 merge_sort() にバグがあるからでしょうね。