マージソートのプログラムで最終的なソート結果のみを表示させたい

前提・実現したいこと

数値データを読み込んでマージソートを行うプログラムを作成しているのですが、最終的なソート結果のみを表示させるようにしたいです。

発生している問題・エラーメッセージ

最終的なソート結果のみを表示させたいが、途中のソート結果も表示されてしまう。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <sys/time.h>

int debug = 1;

double gettime(){
  struct timeval tp;
  double ret;
  gettimeofday(&tp, NULL);
  ret = (double)(tp.tv_sec & 0x00ffffff) + (double)tp.tv_usec / 1000000;
  return ret;
}

int *gamm;

int *merge( int *alpha, int n, int *beta, int m ){
  int gamm_used = 0;
  int i, j;

  i = 0; j = 0;
  while ( i < n && j < m ){
    if ( alpha[i] <= beta[j] ) gamm[ gamm_used++ ] = alpha[ i++];
    else gamm [ gamm_used++ ] = beta[ j++ ];
  }
  if ( i < n && j >= m ){
    while( i < n ) gamm[ gamm_used++ ] = alpha[ i++ ];
  }
  if ( i >= n && j < m ){
    while ( j < m ) gamm[ gamm_used++ ] = beta[ j++ ];
  }

  for(i = 0; i < n; i++){
    alpha[i] = gamm[i];
  }
  
  for(j = 0; j < m; j++){
    beta[j] = gamm[n+j];
  }

  for(i = 0; i < n+m; i++){
    printf("%d\n", gamm[i]);
  }
  
  
  return alpha;
}

int * m_sort( int *a, int i, int j ){
  int k;
  if ( i == j ) return &a[i];
  k = (i+j-1) / 2;
  return merge ( m_sort( a, i, k ), k-i+1, m_sort( a, k+1, j ), j-(k+1)+1 );
}

int main( int argc, char *argv[]){
  char *datafile;
  FILE *fp;
  int n;
  int *data;
  int i;
  
  if ( argc <= 1 ){
    fprintf( stderr, "##### ファイルを指定してください\n" );
    return 1;
  }
  datafile = argv[1];

  if( argc <= 2){
    fprintf( stderr, "##### データ数を指定してください\n");
    return 1;
  }
  n = atoi( argv[2] );

  data = (int *)malloc( n * sizeof(int) );
  gamm = (int *)malloc( n * sizeof(int) );
  fp = fopen( datafile, "r" );
  for (i = 0; i < n; i++){
    fscanf( fp, "%d", &data[i] );
  }
  fclose( fp );

  m_sort( data, 0, n-1 );
  
  free ( data );
  free ( gamm );

  return 0;
}

試したこと

int *merge()の最後の部分、for(i = 0; i < n+m; i++){ ...の部分を試行錯誤しているのですが、最終的なソート結果のみの表示になりません。
読み込むファイルはmerge-data.datと言う名前で、ファイルの中身は以下の通りです。

22
17
6
21
47
9
3
33

まず $ gcc -Wall -o merge merge.c をコンパイルし、
$ ./merge merge-data.dat 8 をコンパイルします。

上のソースコードでの実行結果は以下の通りです。

3
33
9
47
3
9
33
47
6
21
17
22
6
17
21
22
3
6
9
17
21
22
33
47

この最終結果、
3
6
9
17
21
22
33
47
のみを表示させたいです。

補足情報（FW/ツールのバージョンなど）

Cygwin64

行動規範の内容に同意します

回答1件

ベストアンサー

こんばんわ。

考え方としては　merge 関数中のprintf文をコメントアウトし、

main関数のdataをfreeする直前でdataの中身を表示すればよいのではないでしょうか。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <sys/time.h>

int debug = 1;

double gettime(){
  struct timeval tp;
  double ret;
  gettimeofday(&tp, NULL);
  ret = (double)(tp.tv_sec & 0x00ffffff) + (double)tp.tv_usec / 1000000;
  return ret;
}

int *gamm;

int *merge( int *alpha, int n, int *beta, int m ){
  int gamm_used = 0;
  int i, j;

  i = 0; j = 0;
  while ( i < n && j < m ){
    if ( alpha[i] <= beta[j] ) gamm[ gamm_used++ ] = alpha[ i++];
    else gamm [ gamm_used++ ] = beta[ j++ ];
  }
  if ( i < n && j >= m ){
    while( i < n ) gamm[ gamm_used++ ] = alpha[ i++ ];
  }
  if ( i >= n && j < m ){
    while ( j < m ) gamm[ gamm_used++ ] = beta[ j++ ];
  }

  for(i = 0; i < n; i++){
    alpha[i] = gamm[i];
  }

  for(j = 0; j < m; j++){
    beta[j] = gamm[n+j];
  }

// delete
//  for(i = 0; i < n+m; i++){
//    printf("%d\n", gamm[i]);
//  }


  return alpha;
}

int * m_sort( int *a, int i, int j ){
  int k;
  if ( i == j ) return &a[i];
  k = (i+j-1) / 2;
  return merge ( m_sort( a, i, k ), k-i+1, m_sort( a, k+1, j ), j-(k+1)+1 );
}

int main( int argc, char *argv[]){
  char *datafile;
  FILE *fp;
  int n;
  int *data;
  int i;

  if ( argc <= 1 ){
    fprintf( stderr, "##### ファイルを指定してください\n" );
    return 1;
  }
  datafile = argv[1];

  if( argc <= 2){
    fprintf( stderr, "##### データ数を指定してください\n");
    return 1;
  }
  n = atoi( argv[2] );

  data = (int *)malloc( n * sizeof(int) );
  gamm = (int *)malloc( n * sizeof(int) );
  fp = fopen( datafile, "r" );
  for (i = 0; i < n; i++){
    fscanf( fp, "%d", &data[i] );
  }
  fclose( fp );

  m_sort( data, 0, n-1 );

// add 
  for(i = 0; i < n; i++){
    printf("%d\n", data[i]);
  }

  free ( data );
  free ( gamm );

  return 0;
}

投稿2021/12/28 10:20