データ構造とアルゴリズム

担当 ： 藤本 忠博

演習課題

• プログラムの作成
  
  
  1. 自分のホームディレクトリの下に演習用のディレクトリ da を作成する．
     
     
  2. 教科書の５つのソートアルゴリズム（選択ソート，挿入ソート，ヒープソート，クイックソート，マージソート）について，教科書を参考にしてプログラムを作成する．
     
     
  3. 以下のファイルをダウンロードして利用してよい．
     これらのうち，選択ソートについては完成しており，実行できる状態になっている．
     他のソートについては，雛形のみの状態なので，完成させる． ただし，必ずしも雛形に従う必要はない．
     
     
     • ヘッダファイル sort.h
     • メイン関数 sort-main.c
     • データを扱う関数群など sort-funcs.c
     • 選択ソート（アルゴリズム 5.1） algo5-1.c
     • 挿入ソート（アルゴリズム 5.2） algo5-2.c 雛形のみ
     • ヒープソート（アルゴリズム 5.5） algo5-5.c 雛形のみ
     • クイックソート（アルゴリズム 6.1） algo6-1.c 雛形のみ
     • マージソート（アルゴリズム 7.3） algo7-3.c 雛形のみ
     
     
  4. 例えば，選択ソート（algo5-1.c）を実行したい場合，次のようにコンパイルして実行する．
     
     

     h27jXXX@:esrm0001-U:~/da[1] >cc sort-main.c sort-funcs.c algo5-1.c -o sort-main h27jXXX@:esrm0001-U:~/da[2] >sort-main

     
     他のソートを実行したい場合，ファイル sort-main.c 中で，適宜，切り替える． コンパイルするファイルも，適宜，変更する．
     
     

     // **** ソート // アルゴリズム 5.1 選択ソート selectionsort( N, A ); // アルゴリズム 5.2 挿入ソート // insertionsort( N, A ); // アルゴリズム 5.5 ヒープソート // heapsort( N, A ); // アルゴリズム 6.1 クイックソート // quicksort( A, 0, N-1 ); // アルゴリズム 7.3 マージソート // mergesort( A, 0, N-1 );

     
     
  5. ヘッダファイル sort.h 中の次のマクロの値は，適宜，変更する．
     
     

     // データの個数 #define N 10 // 正確な計算時間を得るための反復回数 #define REP 3

     
     
  6. 特に，計算時間を計測する実験のためにマクロ N と REP の値を大きくした場合，ファイル sort-main.c 中の k のループ内で行っているデータと計算時間の表示が大量に出るので，コメントアウトして表示が出ないようにするとよい．
     
     
  7. ファイル sort-funcs.c 中で３通りのデータ入力の関数が定義されている．
     ファイル sort-main.c 中で，適宜，これらを切り替える．
     
     

     // **** データの入力 // ランダム data_random( N, A ); // 昇順 // data_ascending( N, A ); // 降順 // data_descending( N, A );

     
     
• プログラム例
  
  
  • ヒープソートの関数 delete_maximum の実装について
    教科書のアルゴリズム 5.4 の関数 delete_maximum 中の「T[1]を出力;」と「アルゴリズムを終了;」の実現方法について，具体的な実装例を載せます．
    　→　delete_maximum.c
    教科書では，関数の最初のところで「T[1]を出力;」がありますが，ここで return( T[1] ); としてしまうと関数の実行が終わってしまうので，この実装例では，最初のところで T[1] の値を変数 max に入れておいて，最後に return( max ); として値を返しています． また，２箇所の「アルゴリズムを終了;」については，それぞれの箇所で return( max ); としても良いのですが，この実装例では，それぞれの箇所で break; によって while ループを抜け，最後に return( max ); としています．参考にしてください．
    
    
• 実験
  
  以下の条件で計算時間の計測を行う．マクロ N と REP を適切な値に設定すること．
  それぞれの条件で計測した計算時間から，横軸をデータサイズ（個），縦軸を計算時間（秒）としてグラフを作成する．
  
  
  1. ５つのアルゴリズムの計算時間を比較する．
     教科書の p.70 の図6.7のように，データサイズー計算時間のグラフを作成する．
     入力データは　ランダム　にする．
     
     
     1. ５つのアルゴリズムの全てを比較　⇒　グラフA-1
     2. 時間計算量が O( n log n ) である３つのアルゴリズム（ヒープソート，クイックソート，マージソート）を比較　⇒　グラフA-2
     
     
  2. クイックソート以外の４つのアルゴリズムについて，入力データの違いが計算時間にどのように影響するかを調べる．
     ４つのアルゴリズムのそれぞれについて，入力データを　ランダム，　昇順，　降順　の３通りに変えて，データサイズー計算時間のグラフを作成する．
     
     
     1. 選択ソート（同じグラフ上にランダム，昇順，降順の結果を載せる）　⇒　グラフB-1
     2. 挿入ソート（同上）　⇒　グラフB-2
     3. ヒープソート（同上）　⇒　グラフB-3
     4. マージソート（同上）　⇒　グラフB-4
     
     
  3. クイックソートについて，上記の B と同様，入力データの違い（ランダム，昇順，降順）が計算時間にどのように影響するかを調べる．
     ただし，同時に，基準値となるデータを選ぶ方法による影響も調べる．
     ソートの対象とするデータ D[left], ..., D[right] の中から基準値となるデータを選ぶ方法を次の５通りに変えて，それぞれ，データサイズー計算時間のグラフを作成する．
     
     
     1. 方法1：データ D[left], ..., D[right] の中からランダムに選ぶ（同じグラフ上にランダム，昇順，降順の結果を載せる）　⇒　グラフC-1
     2. 方法2：真ん中のデータ D[(left+right)/2] を選ぶ（同上）　⇒　グラフC-2
     3. 方法3：３つのデータ D[left], D[(left+right)/2], D[right] を大きさの順に並べて中央のデータを選ぶ（同上）　⇒　グラフC-3
     4. 方法4：左端のデータ D[left] を選ぶ（同上）　⇒　グラフC-4
     5. 方法5：右端のデータ D[right] を選ぶ（同上）　⇒　グラフC-5
     
     
  グラフはどのような方法で作成してもよい．
  LibreOffice Calc を使う場合には，この雛形ファイルを参考に（グラフの種類は散布図）．　→　graph.ods
  コマンドラインから実行する場合には "soffice -calc graph.ods"
  このグラフは LibreOffice Writer で作成する文書ファイルに貼り付けることができる．
  コマンドラインから実行する場合には "soffice -writer"
  
  
• レポート
  
  
  • レポートの内容：
    • 上記の実験 A，B，C のそれぞれについて，作成したグラフを掲載し，グラフに基づく考察を書く．
    • プログラムのソースコードをレポートの最後に掲載する． 自分で書いたもの（挿入ソート，ヒープソート，クイックソート，マージソート）だけでよい．
    • レポートの表紙には，科目名（データ構造とアルゴリズム）と自分の入学年度，学籍番号，氏名を忘れずに書く．
    
    
  • 提出方法： 上記の内容を１つのＰＤＦファイルにして（ソースコードも別のファイルにはしない），藤本忠博（fujimoto@cis.iwate-u.ac.jp）宛てにメールに添付して提出する．
    
    
  • 提出期限： 令和3年1月29日（金）
    
    
  • レポートの提出の確認：レポートの提出状況は下のリンク先に掲載するので，確認してください． メールへの返信は行いません． 提出後，数日が経っても未提出となっている場合，授業の際に言ってください．
    
    
  • 単位取得のためには必ずレポートを提出してください． レポートが未提出の場合，単位は出しません．

授業アンケート

期末試験

• 試験日時：令和3年2月2日(火)　10:30 〜 12:10　４号館西棟106室
• 教科書，プリント，ノートなど，すべて持ち込み不可．

過去の期末試験問題

• 2016年度 問題
• 2017年度 問題
• 2018年度 問題
• 2019年度 問題
• 2020年度 問題