データ構造とアルゴリズムⅡ (2022年度) レポート課題 2

ソーティングの計算量に関する考察

▼目的

単純なソーティングアルゴリズムに続いて、シェルソート、クィックソート、マージソート、ヒープソートを学修してきた。そこで、実際に、これらのソーティングアルゴリズムを実装し、入力データとしてランダムデータ、ソート済みデータを使い、 プログラム中の比較操作・交換操作に相当する行の実行回数を計測する。計測した結果からアルゴリズムの計算量についての考察を行うことを目的とする。ただし、実装するソーティングアルゴリズムは、降順にソートするものとする。

▼課題

指定されたソーティングアルゴリズムを実装し、プログラム中の比較操作・交換操作に相当する行の実行回数を計測し、計算量について考察せよ。また、使用したソーティングのプログラムリストを添付せよ。

学籍番号の下1桁によって、考察するソーティングアルゴリズムを次のように指定する。

下1桁が1, 5, 9の人　：　シェルソート
下1桁が2, 6, 0の人　：　クイックソート
下1桁が3, 7の人：　マージソート
下1桁が4, 8の人：　ヒープソート

▼提出締切と提出先

6月30日17時までに、指示された提出先へ提出せよ。

▼条件

添付のファイルをレポートのフォーマットです。また、表紙の全てのチェック項目をチェックして、全てが○であること。表紙のダウンロード(Word)
データが昇順にソートされている場合、降順にソートされている場合、および、ランダムな場合の3種類について、プログラム中の比較操作・交換操作に相当する行の実行回数を計測せよ。ただし、s[0], s[1], ... といった各行の実行回数のカウンタは不要とするので、必要な部分にだけカウンタを入れること。また、ソースコードのどこで（どの変数で）、比較操作・交換操作をカウントしているかを明記すること。
入力データ数は、100、200、300、400、500とか、1000、2000、3000、4000、5000　とかを使用し、計算量の議論やグラフ作成上の都合に応じて、これら以外の値も積極的に使用せよ。

時間計算量は、入力データが昇順・降順・ランダムの３つの場合のそれぞれについて、交換操作と比較操作に分けて述べること。結論は、次のような表にまとめること。

入力データ	比較の時間計算量	交換の時間計算量
昇順	O(?)	O(?)
降順	O(?)	O(?)
ランダム	O(?)	O(?)

なお、計算量を上記3の表にまとめる前に、計測した「実行文の実行回数」をもとに、入力データ数によって比較操作と交換操作の実行回数がそれぞれどう変化しているかに着目して、そのように結論づける理由を述べよ。教科書p.192のTable12.1, 12.2なども議論の参考にして良い。
重要なことは、入力データ数が 2倍になったとき、実行回数が 2 倍になるのか、それとも4倍になるのか。入力データ量が3倍になればどうなるのか、それはなぜなのかを考えることである。
単に「グラフを見ると y = x log x の形をしているので、O(x log x)である。」といった乱暴な結論ではダメ。
また、「内側のループが何回まわって、外側のループが何回まわるから…」といったプログラムの動作説明は教科書に書かれているので、その詳細をレポートに書き写すことは不要である(これらを理解していることは、当然の前提である)。
議論の参考のために、gnuplot, OpenOffice Calc, Excel などのグラフ描画機能を利用し、グラフを作成せよ。
手書きは不可とする。
整列のプログラムは原則として教科書に掲載されているものを用いること。別のプログラムを用いてもよいが、その場合には教科書のプログラムとの差異（例えば、降順の整列である、教科書のプログラムと比べてピボットの取り方を改良したアルゴリズムである、など）をレポートに明記すること。
マージソートの場合の交換回数は、データを移動した回数をカウントとせよ。
次のような、O(n2)の議論に使えない不適切なグラフを描いたレポートは再提出を求める。

n2の形をしていない

横軸の値(100, 500, 1000,,,)が等間隔である

また、グラフの軸の名前がない場合、軸の数値がおかしい場合も原則差し戻すので、注意すること。

参考

gnuplot とは、unix上でグラフを作成するツールである。 2次元ならば xy座標をファイルに入れておいて(プログラムで作成しておいて)、それを読ませることで、グラフが作成される。使い方は、下記のページを参照せよ。

サンプルコード（C言語）

次の例は、バブルソートによる整列プログラム (p.186 List12.1参考)に、比較回数、交換回数を計測するために、comp++, swap++を挿入した例である。

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

#define MAX_ELEMENTS    10000 /* 最大のデータ数 */  
#define OFFSET          100   /* データ数の増分値 */  
#define MAX_LINES       10    /* 関数の最大行数 */  
  
int  a[MAX_ELEMENTS] ;        /* 探索するデータ領域 */  
  
int  comp, swap      ;        /* 比較回数、交換回数を格納する変数 */  
  
void bubble_sort(int a[], int n);  
void init_step(void);  
void print_step(int);  
void print_header(char *);  
int sorted(int);  
  
int main(void){  
  int i;  
  int n; /* データ数 */  
  
  srandom(time(0));           /* 乱数の種を初期設定する */  
  
 /* ランダム入力の場合 */  
  print_header("random");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = random() % n ;    /* 配列要素に乱数値を設定する */  
    }  
  
    bubble_sort(a, n);         /* バブルソートを実行 */  

    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */


    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 昇順にソートされた入力の場合 */  
  print_header("ascending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = i ;               /* 配列要素に昇順のデータ値を設定する */  
    }  
  
    bubble_sort(a, n);         /* バブルソートを実行 */  

    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */

    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 降順にソートされた入力の場合 */  
  print_header("descending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = n - i ;           /* 配列要素に降順のデータ値を設定する */  
    }  
  
    bubble_sort(a, n);         /* バブルソートを実行 */  

    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */

    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
  return 0;  
}  
  
void init_step(void){  
  swap = 0; comp = 0;  
}  
  
void print_header(char *s) {  
  printf("%s\n   n, 比較回数, 交換回数, チェック", s);  
  printf("\n");  
}  
  
void print_step(int n){  
  printf("%4d, %8d, %8d", n, comp, swap);  
  
  if (sorted(n)) { /* 配列が昇順に整列されているかチェック */  
    printf(", sorted\n");  
  } else {  
    printf(", unsorted\n");  
  }  
}  
  
int sorted(int n) {  
  int i;  
  for (i=0; i < n-1; i++)  
    if (a[i] > a[i+1]) return 0;  
  return 1;  
}  
  
void bubble_sort(int a[], int n){  
  int i, j, t;  
  
  for (i = 0; i < n - 1; i++) {  
    for (j = n - 1; j > i; j--) {  
      comp++;  
      if (a[j-1] > a[j]) {  
        swap++;  
        t = a[j]; a[j] = a[j-1]; a[j-1] = t;  
      }  
    }  
  }  
}

サンプルプログラムの出力

次の例は、サンプルプログラムの出力の一部である。このように,(カンマ)で区切られたデータを用意することで、表計算ソフトに手でデータを一つずつ入力（あるいはコピー）する手間を省くことができる。具体的には、次のような操作をすればよい。プログラムの出力をコピーしてテキストファイルに保存し、そのテキストファイルの拡張子を.csv　にする。次にそのCSVファイルを Excel で開いて、行と列を転置すれば、実行回数の変化のグラフを描きやすい形でデータをまとめることができる。
（転置しなくても、メニューからグラフツール→デザイン→データ選択　で横軸を n の値に設定しなおせばよい。）

  n, 比較回数, 交換回数, チェック  
100,     4950,     2411, sorted  
200,    19900,     9440, sorted  
300,    44850,    21879, sorted  
400,    79800,    38021, sorted  
500,   124750,    64465, sorted  
600,   179700,    91450, sorted  
...