データ構造とプログラミング（第2回）

データ構造とプログラミング
（第３回）
大岩元
ＴＡ: 武田林太郎
ＳＡ: 明石敬
バブルソート
• 左から、隣同士比較して必要なら入れ替える
これを繰り返す
• 不変項： out の右側はソート済
• 比較回数は N*(N-1)/2 -> O(N**2)
• 入れ替えはランダムなら約N**2/4 (逆順なら
比較と同回数）
選択ソート
• 最小値を見つけ、先頭と入れかえる。これを
残りに対して繰り返す。
• 不変項： out より左はソート済
• 比較回数は N*(N-1)/2 -> O(N**2)
• 入れ替えは N 回 -> 無視してよい
挿入ソート
• 不変項： out の左側はソート済
• 未ソートの左端の項目をソート済の適当な所
に挿入する
• 最大比較回数は N*(N-1)/2 -> O(N**2)
• 平均比較回数は N*(N-1)/4
• 入れ替えは N
状態遷移機械としてのプログラム
• プログラムは変数と命令から成る
• コンピュータは命令を読み出しながら、変数
の内容を書き換えていく
• 変数の値（の集合）が状態を表わしている
• 計算とは命令の実行によって（変数の）状態
を変えていくことである
• 変数の状態変化を示す表をトレース表と呼ぶ
番兵
• a[0] から a[N-1] の中で searchkey をさが
す
a[N] = searchkey; i = 0;
while(true) {
if (a[i] == searchkey) break; i++
}
if (i = N) found = false else found = true;
演習問題
• 各ソートプログラムのトレース表を作れ
• 普通の線形探索と番兵を使ったものでは、比
較回数がどのように減るか
• 挿入ソートに番兵を組み込んで、速度を向上
させよ
• 講義・演習の感想を書け

Download Report