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

データ構造とアルゴリズム論
第５章整列（ソート）
のアルゴリズム
平成27年6月12日
森田彦
理解度チェック１
まず、ファイル入出力を行うために、プログラムの冒
頭にあるインポート文を付加しなければなりません。
空欄に入るパッケージ名は次の選択肢のいずれでし
ょうか？
import
１．javax.swing.*
２．javax.awt.event.ActionEvent
３．java.io.*
４．java.util.*
;
理解度チェック１解答
空欄に入るパッケージ名は？
１．javax.swing.*
２．navax.awt.event.ActionEvent
３．java.io.*
４．java.util.*
ファイル入出力を行うためには、「java.io.*」と
いうパッケージをインポートする（p.36参照）。
ioは「input/output」、つまり入出力の略。
理解度チェック２
空欄［問題２］に入る適切な用語は次のいずれで
すか？
１．Nenrei.txt
４．score.txt
２．output.txt
５．Age.txt
３．input.txt
理解度チェック２解答
問題２に入る適切な用語は次のいずれですか？
１．Nenrei.txt
４．score.txt
２．output.txt
５．Age.txt
３．input.txt
空欄には、入力ファイル名が入る。
問題文にある通り、今の場合は Age.txt
理解度チェック３
空欄［問題３］に入る適切な式は次のいずれで
すか？
１．NenreiFile.readLine()
２．AgeFile.readLine()
３．fin.readLine()
４．fout.readLine()
理解度チェック３解答
問題３に入る適切な式は次のいずれですか？
１．NenreiFile.readLine() ２．AgeFile.readLine()
３．fin.readLine()
４．fout.readLine()
空欄に入るのは、データを1行分読み取る命令
入力ストリーム名．readLine();
BufferedReader
AgeFile=new BufferedReader(･･･
より・・・
AgeFile.readLine()
理解度チェック４
空欄［問題４］に入る適切な式は次のいずれで
すか？
１．NenreiFile.close()
２．AgeFile.close()
３．fin.close()
４．fout.close()
理解度チェック４解答
問題４に入る適切な式は次のいずれですか？
１．NenreiFile.close() ２．AgeFile.close()
３．fin.close()
４．fout.close()
ファイルを閉じるには、
入出力ストリーム名．close();
BufferedReader
AgeFile=new BufferedReader(･･･
より・・・
AgeFile.close
ソートとは？
 幾つかのデータを、一定の基準（大きい順、
小さい順等）に従って並べ替える操作
昇順
（小さい順）
降順
（大きい順）
アルゴリズム
の宝庫
アルゴリズム論学習の山場！
本章（本日）の学習のねらい
① 基本的なソートアルゴリズムを学習し、その処
理の流れを理解する。
→ バブルソート、選択ソート、挿入ソート
② ３つのソートアルゴリズムの効率について考
察する。
③ ソートアルゴリズムを実際のプログラムに応用
する。
5-1 バブルソート
 隣り合う２つのデータを比較し、「並べたい
順になっていなければ入れ替える」という
操作を繰り返す。
デモプログラム
＜処理の流れ－４つのデータの昇順の場合＞
A
[0]
[1] [2]
[3]
10
9 12
2
ソート開始
10
9 12
2
A[0]＞A[1]なので交換する。
9
10 12
2
A[1]＜A[2]なので交換しない。
9
10 12
2
A[2]＞A[3]なので交換する。
9
10
2 12
A[3]の値確定。
9
10
2 12
A[0]＜A[1]なので交換しない。
9
10
2 12
A[1]＜A[2]なので交換する。
9
2 10 12
A[2]の値確定。
9
2
10 12
A[0]＞A[1]なので交換する
2
9
10 12
A[0],A[1]の値確定。→完了！
アルゴリズムの整理
 A[0]～A[n-1]のデータをソートする場合。
 データの末尾から順番に値が確定して行く。
（右端）
A[0],A[1],・・・,A[i],・・・,A[n-2],A[n-1]
 A[i]の値を確定するためには、A[0]～A[i]まで
の比較が必要。→i回の比較
 A[i] ｛i=n-1,n-2,・・・,1｝を確定するために
A[j]＞A[j+1]の判定を｛j=0～i-1｝について行う。
2重のループが必要 → プリント p.81参照。
この流れ図の理解が本日のポイント！
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.89参照
5-3 挿入ソート
 部分的に整列されている場合に効果的
例：A[1]～A[3]が整列済み（昇順）
[1] [2]
[3] [4] [5]
正しい位置に
余分な比較をし
なくて良い。
A 1
2
3
9
5
A[4]を挿入 p.93の流れ図参照
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-1)/2
 一般に・・・
比較回数N： Nバブル=N選択≧N挿入
交換回数N： Nバブル=N挿入、 N選択 =ｎ-1
バブルソートが最も効率が悪い。
一般には、挿入ソートが効率が良い場合
が多い。
プリント5-4
節参照！
学習に当たって
 ソート（処理）はアルゴリズム論の山場となる重
要なところです。
 各ソートの処理の流れを、シミュレーションプロ
グラムを利用してよく理解して下さい。
 本日の学習のポイントは、各ソートの流れ図を
理解できるかどうかです。→トレースして流れを
確認できればOK
 理解できない場合は「どの部分が理解できない
のか？」を自分なりにしぼって質問して下さい。
 【応用課題5-A】まで終えたら、演習を終えて結
構です。
位置が
決定す
る要素
順序の決まり方（整理）
A[0] A[1] ・・・ A[i]
・・・ A[n-2] A[n-1]
i
n-1
A[j]とA[j+1]の比較（と交換）
j=0～n-2
n-2
A[j]とA[j+1]の比較（と交換）
j=0～n-3
・・・
i
A[j]とA[j+1]の比較（と交換）
j=0～ ?i-1
・・・
2
A[j]とA[j+1]の比較（と交換）
j=0～1
1
A[j]とA[j+1]の比較（と交換）
j=0

Download Report