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

データ構造とアルゴリズム論
第６章整列（ソート）
のアルゴリズム
平成15年11月18日
森田彦
基礎課題提出状況(11/11)
平均提出数=25.6 (全課題数28)
基礎課題提出状況（11/11）
平均提出数=25.6
120
度数（人数）
100
80
60
40
20
0
0～5
6～10
11～15
16～20
提出数範囲
約7割が25題以上を提出
21～25
25～28
応用課題提出状況（11/11）
平均提出課題数＝8.0
応用課題提出状況（11/11）
平均提出数＝8.0
45
40
35
度数（人数）
30
25
20
15
10
5
0
0
1～４
5～8
9～12
13～16
提出数範囲
13題以上提出は約22%
17～20
21～23
ソートとは？
 幾つかのデータを、一定の基準（大きい順、
小さい順等）に従って並べ替える操作
昇順
（小さい順）
降順
（大きい順）
アルゴリズム
の宝庫
アルゴリズム論学習の山場！
本章（本日）の学習のねらい
① 基本的なソートアルゴリズムを学習し、その処
理の流れを理解する。
→ バブルソート、選択ソート、挿入ソート
② ３つのソートアルゴリズムの効率について考
察する。
③ ソートアルゴリズムを実際のプログラムに応用
する。
6-1 バブルソート
 隣り合う２つのデータを比較し、「並べたい
順になっていなければ入れ替える」という
操作を繰り返す。
デモプログラム
＜処理の流れ－４つのデータの昇順の場合＞
A
[1]
[2] [3]
[4]
10
9 12
2
ソート開始
10
9 12
2
A[1]＞A[2]なので交換する。
9
10 12
2
A[2]＜A[3]なので交換しない。
9
10 12
2
A[3]＞A[4]なので交換する。
9
10
2 12
A[4]の値確定。
9
10
2 12
A[1]＜A[2]なので交換しない。
9
10
2 12
A[2]＜A[3]なので交換する。
9
2 10 12
A[3]の値確定。
9
2
10 12
A[1]＞A[2]なので交換する
2
9
10 12
A[1],A[2]の値確定。→完了！
アルゴリズムの特徴
 A[1]～A[n]のデータをソートする場合。
 データの末尾から順番に値が確定して行く。
A[n]→A[n-1],･･･,A[i],・・・,A[2]
 A[i]の値を確定するためには、A[1]～A[i]まで
の比較が必要。→(i-1)回の比較
 A[i] ｛i=n,n-1,・・・,2｝を確定するために
A[j]＞A[j+1]の判定を｛j=1～i-1｝について行う。
2重のループが必要 → プリント p.89参照。
※ A[0]～A[n-1]としている。
6-2 選択ソート
 ＜考え方－昇順の場合＞
10
9
6
2
ソート開始時
10
9
6
2
最小値（の位置）を見つける
10
9
6
2
2
9
6 10
1番目のデータと交換する
1番目データの値確定
2
9
6 10
最小値（の位置）を見つける
2
9
6 10
2番目のデータと交換する
2
6
9 10
2番目データの値確定
という操作を繰り返す。
流れ図→p.97参照
6-3 挿入ソート
 部分的に整列されている場合に効果的
例：A[1]～A[3]が整列済み（昇順）余分な比較をし
なくて良い。
[1] [2] [3] [4] [5]
A 1
2
3
9
5
A[4]を挿入 p.101の流れ図参照
1
2
3
9
5
A(3)＜A(4)なので交換しない
1
2
3
9
5
A(1)～A(4)まで整列済み
1
2
3
9
5
A(5)を挿入
1
2
3
9
5
A(4)＞A(5)なので交換する
1
2
3
5
9
A(3)＜A(4)なので交換しない
1
2
3
5
9
ソート完了！
6-4 アルゴリズムの効率
 比較回数と交換回数が少ないほど、効率
は良い。
全てのペアについて比較
 一般に・・・
選択ソート
比較回数N： Nバブル=N選択≧N挿入
交換回数N： Nバブル=N挿入≧N選択 (=ｎ-1)
整列済みデータの場合は、逆転する場合あり
バブルソートが最も効率が悪い。
挿入ソートが効率が良い場合が多い。
Windows updateについて
 2003年11月12日(日本時間)、マイクロソフ
ト社より深刻度が緊急とされるセキュリ
ティ上の修正プログラムが公開。
 修正プログラムが適用されていないシス
テムは、侵入やワームによる感染などの
被害を受ける可能性があります。
 各自速やかに、Windows updateを実行し
て下さい。

Download Report