トップページ > 題目ごとのヒント > 題目4: ソーティングアルゴリズム

題目4: ソーティングアルゴリズム

一般的ヒント

配列とポインタの関係がよく分かりません．2つは同じなんですか？

本題目のヒント

時間の測定について

平均時間の測定について:
バブルソートとクイックソートの実行速度は大きく異なるため，平均時間の測定では両者のデータ数を揃える必要はない．ただし，どちらも少なくとも1秒以上の時間はかかる程度のデータ数 で実験すること．
最悪時間の測定について:
クイックソートの場合，データ数が多くなると最悪ケースでは実行時エラーで止まってしまうことがあるので注意すること (再帰呼出しの深さが深くなりすぎ，スタック領域を使い尽くすため)

予習課題について

「データ構造とアルゴリズム」のテキストを参照するとよい．

レポートでの結果の説明と考察

実行時間をまとめた表を作成し，その上で実行時間を縦軸，データ数を横軸とするグラフをアルゴリズムごとに描いて，両者の実行時間の増加の様子を確認する．

表やグラフでは，番号やタイトルを付ける，単位を付けるといった事項を忘れないこと (よくあるミスや以下の画像を参照)．

適切な表の例:
不適切な図の例:
適切な図の例:

グラフを手書きする場合はグラフ用紙を使用すること．グラフを Excel 等で作成する場合，横軸 (データ数) の取り方が一定間隔となるよう，注意すること．

考察は，例えば以下のように具体的に記述すること．

バブルソートの最悪ケースでは，データ数を 10000 から 20000 へ 2倍に増やすと，実行時間は 1.2 [秒] から 4.7 [秒] へと約22倍 (≒3.91倍) となっている (表△)．同様に○○から△△への増加でも約22倍 (≒☆☆倍) となっており，実データからも最悪計算量が O(n²) であることを確認できた．

なお，O(n log n) に関し，n が大きいと log n はほとんど増加しないため，実行時間はデータ数の増加にほぼ比例するといってよい (データ数を2倍にしても実行時間も2倍程度にしかならない)．

プログラムソースのひな型および実行例

実験1

プログラムソースのひな型

#include <stdio.h>
#include <stdlib.h>

/* 実験 1 で作成 */
void bubble_sort( int a[], int n ){
  int i, k;
  for ( k = 1; k < n; k++ ){
    for ( i = 0; i < (n-k); i++ ){
      if ( a[i] > a[i+1] ){
	/* 内容は自分で作る */
      }
    }
  }
}

/* 配列の内容が昇順に並んでいるかチェックする */
void check( int a[], int n ){
  int i;

  for ( i = 0; i < (n-1); i++ ){
    if ( a[i] > a[i+1] ){
      printf("NG: この配列は昇順に並んでいません\n");

      /* void 関数の場合，return とだけ書くとそこで関数は終了 */
      return; 
    }
  }

  printf("OK: この配列は昇順に並んでいます\n");
}

int main(int argc, char* argv[]){
  int i, n, seed;
  int* a;

  if ( argc < 3 ){
    printf("*** エラー: コマンドライン引数に乱数の種と配列の長さを指定して下さい\n");
    return 1;
  }
  
  seed = atoi(argv[1]);
  printf("乱数の種 = %d\n", seed);
  srand( seed );

  n = atoi(argv[2]);
  printf("配列の長さ = %d\n", n);

  a = (int*) calloc( n, sizeof(int) );
  if ( NULL == a ){
    printf("配列のメモリ確保に失敗しました\n");
    return 1;
  }

  for ( i = 0; i < n; i++ ){
    a[i] = rand();
  }

  printf("\n初期状態を確認 --> ");
  check(a,n);

  printf("\n### バブルソートを実行 ###\n");
  bubble_sort(a,n);

  printf("\n再度確認 --> ");
  check(a,n);

  free(a);

  return 0;
}

実行例

$ ./a.out 3 10
乱数の種 = 3
配列の長さ = 10

初期状態を確認 --> NG: この配列は昇順に並んでいません

### バブルソートを実行 ###

再度確認 --> OK: この配列は昇順に並んでいます

実験2

プログラムソースのひな型

#include <stdio.h>
#include <stdlib.h>

/* 実験 2 で作成 */
int partition(int a[], int n, int i, int j) {
  /* 実験テキストを参照 */
}

/* 実験 2 で作成 */
void quick_sort(int a[], int n, int i, int j) {
  int m;

  if ( i < j ) {
    m = partition( a, n, i, j );
    quick_sort( a, n, i, m-1 );
    quick_sort( a, n, m+1, j );
  }
}

/* 配列の内容が昇順に並んでいるかチェックする */
void check( int a[], int n ){
  int i;

  for ( i = 0; i < (n-1); i++ ){
    if ( a[i] > a[i+1] ){
      printf("NG: この配列は昇順に並んでいません\n");

      /* void 関数の場合，return とだけ書くとそこで関数は終了 */
      return; 
    }
  }

  printf("OK: この配列は昇順に並んでいます\n");
}

int main(int argc, char* argv[]){
  int i, n, seed;
  int* a;

  if ( argc < 3 ){
    printf("*** エラー: コマンドライン引数に乱数の種と配列の長さを指定して下さい\n");
    return 1;
  }
  
  seed = atoi(argv[1]);
  printf("乱数の種 = %d\n", seed);
  srand( seed );

  n = atoi(argv[2]);
  printf("配列の長さ = %d\n", n);

  a = (int*) calloc( n, sizeof(int) );
  if ( NULL == a ){
    printf("配列のメモリ確保に失敗しました\n");
    return 1;
  }

  for ( i = 0; i < n; i++ ){
    a[i] = rand();
  }

  printf("\n初期状態を確認 --> ");
  check(a,n);

  printf("\n### クイックソートを実行 ###\n");
  //quick_sort(a,n);
  quick_sort(a,n, 0, n-1);

  printf("\n再度確認 --> ");
  check(a,n);

  free(a);

  return 0;
}

実行例

$ ./a.out 3 10
乱数の種 = 3
配列の長さ = 10

初期状態を確認 --> NG: この配列は昇順に並んでいません

### クイックソートを実行 ###

再度確認 --> OK: この配列は昇順に並んでいます

実験3(1): バブルソートの場合

以下はバブルソートに関する内容であるが，クイックソートの場合も同様である．

プログラムソースのひな型

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 実験 1 で作成 */
void bubble_sort( int a[], int n ){
  int i, k;
  for ( k = 1; k < n; k++ ){
    for ( i = 0; i < (n-k); i++ ){
      if ( a[i] > a[i+1] ){
	/* 内容は自分で作る */
      }
    }
  }
}


int main(int argc, char* argv[]){
  int i, n, seed;
  int* a;
  clock_t start, end;
  float time;

  if ( argc < 3 ){
    printf("*** エラー: コマンドライン引数に乱数の種と配列の長さを指定して下さい\n");
    return 1;
  }
  
  seed = atoi(argv[1]);
  printf("乱数の種 = %d\n", seed);
  srand( seed );

  n = atoi(argv[2]);
  printf("配列の長さ = %d\n", n);

  a = (int*) calloc( n, sizeof(int) );
  if ( NULL == a ){
    printf("配列のメモリ確保に失敗しました\n");
    return 1;
  }

  for ( i = 0; i < n; i++ ){
    a[i] = rand();
  }

  start = clock();
  bubble_sort(a,n);
  end = clock();

  time = (float)(end - start)/CLOCKS_PER_SEC;
  printf("ソーティングにかかった時間 = %7.3f 秒\n", time);

  free(a);

  return 0;
}

実行例

$ ./a.out 3 20000
乱数の種 = 3
配列の長さ = 20000
ソーティングにかかった時間 =   2.660 秒

実験3(2): バブルソートの場合

以下はバブルソートに関する内容であるが，クイックソートの場合も同様である．

プログラムソースのひな型

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 実験 1 で作成 */
void bubble_sort( int a[], int n ){
  int i, k;
  for ( k = 1; k < n; k++ ){
    for ( i = 0; i < (n-k); i++ ){
      if ( a[i] > a[i+1] ){
	/* 内容は自分で作る */
      }
    }
  }
}


int main(int argc, char* argv[]){
  int i, n;/*, seed;*/
  int* a;
  clock_t start, end;
  float time;

  if ( argc < 2 ){
    printf("*** エラー: コマンドライン引数に配列の長さを指定して下さい\n");
    return 1;
  }
  
  n = atoi(argv[1]);
  printf("配列の長さ = %d\n", n);

  a = (int*) calloc( n, sizeof(int) );
  if ( NULL == a ){
    printf("配列のメモリ確保に失敗しました\n");
    return 1;
  }

  /* 逆順（降順）に並んだデータを用意する */
  for ( i = 0; i < n; i++ ){
    a[i] = n-i;
  }

  start = clock();
  bubble_sort(a,n);
  end = clock();

  time = (float)(end - start)/CLOCKS_PER_SEC;
  printf("ソーティングにかかった時間 = %7.3f 秒\n", time);

  free(a);

  return 0;
}

実行例

$ ./a.out 20000
配列の長さ = 20000
ソーティングにかかった時間 =   2.660 秒