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

データ構造とアルゴリズム論
第5章 整列(ソート)
のアルゴリズム
平成16年11月9日
森田 彦
第1回目テスト結果
平均点=69.0 最高点=97(1名) 最低点=32(1名)
受験総数=135名
第1回目テスト得点分布 受験者総数=135名
最高点=97 最低点=32 平均点=69.0
45
40
度数(人数)
35
30
25
20
次回は挽回を!
10名います。
15
10
5
0
30~39
40~49
50~59
講評はHP参照
60~69 70~79
得点範囲
80~89
90~100
基礎課題提出状況(11/2)
平均提出数=21.7 (全課題数24)
基礎課題提出状況(11/2) 平均=21.7
120
100
度数(人数)
80
60
要注意!
40
20
0
0~5
6~10
11~15
16~20
21~24
提出数
約8割が21題以上を提出
応用課題提出状況(11/2)
平均提出課題数=13.0
応用課題提出状況(11/2) 平均=13.0/22
60
50
度数(人数)
40
30
20
10
0
0
1~5
6~10
11~15
16~20
20~22
提出数
11題以上提出は74%
全
て
提
出
し
た
人
4
名
ソートとは?
 幾つかのデータを、一定の基準(大きい順、
小さい順等)に従って並べ替える操作
昇順
(小さい順)
降順
(大きい順)
アルゴリズム
の宝庫
アルゴリズム論学習の山場!
本章(本日)の学習のねらい
① 基本的なソートアルゴリズムを学習し、その処
理の流れを理解する。
→ バブルソート、選択ソート、挿入ソート
② 3つのソートアルゴリズムの効率について考
察する。
③ ソートアルゴリズムを実際のプログラムに応用
する。
5-1 バブルソート
 隣り合う2つのデータを比較し、「並べたい
順になっていなければ入れ替える」という
操作を繰り返す。
デモプログラム
<処理の流れ-4つのデータの昇順の場合>
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.75参照。
※ A[0]~A[n-1]としている。
5-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.83参照
5-3 挿入ソート
 部分的に整列されている場合に効果的
例:A[1]~A[3]が整列済み(昇順)
[1] [2]
[3] [4] [5]
正しい位置に
余分な比較をし
なくて良い。
A 1
2
3
9
5
A[4]を挿入 p.87の流れ図参照
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
ソート完了!
5-4 アルゴリズムの効率
 比較回数と交換回数が少ないほど、効率
は良い。
全てのペアについて比較
 一般に・・・
選択ソート
比較回数N: Nバブル=N選択≧N挿入
交換回数N: Nバブル=N挿入≧N選択 (=n-1)
整列済みデータの場合は、逆転する場合あり
バブルソートが最も効率が悪い。
挿入ソートが効率が良い場合が多い。