整列（ソート，
sort）
•
列を昇順や降順に並べ替えること
• 列にはレコード群を想定するとよい．
• 大小（前後）関係はキーによる．
• 非常に多くの場面で利用される．
•
内部ソート
• 主記憶に記憶された配列をソート
•
外部ソート
• 外部媒体へのアクセスを前提
ソーティングの計算量
•
計算量：
アルゴリズムの効率を評価する尺度
•
計算にどれくらい手間がかかるかを評価
•
キーの比較回数
Cとレコードの置換回数
Mで 評価する．
•
キーの比較回数が少ないものが高速
•
置換回数は比較回数で抑えられる（
C ≧ M）
•
漸近的計算量で評価することが多い．
講義で扱うソートの前提
1.
レコード群は，整数型
(int)の配列とする．
（簡単のため，講義ではキーのみを扱う）
2.
ソートにより，配列を昇順に並べることを考える．
単純選択法
単純選択法
基本的な考え方
1.
全体で最小要素を選出して，
それを左端に移動．
2.
次に，それを除いた残りの中から
最小要素を選出．．．
単純選択法
具体的には
配列番号を
iとする．
（検索後の最小要素を入れる．）
以下をi=0～N-2について繰り返し
a[i]～a[N-1]の中から最小要素a[k]を検
索し，a[i]と交換
単純選択法
実行例
i=0 6 9 12 7 15 23 2 10 4 20 i=1 2 9 12 7 15 23 6 10 4 20 i=2 2 4 12 7 15 23 6 10 9 20 i=3 2 4 6 7 15 23 12 10 9 20 i=4 2 4 6 7 15 23 12 10 9 20 i=5 2 4 6 7 9 23 12 10 15 20 i=6 2 4 6 7 9 10 12 23 15 20 i=7 2 4 6 7 9 10 12 23 15 20 i=8 2 4 6 7 9 10 12 15 23 20 2 4 6 7 9 10 12 15 20 23
単純選択法の計算量
•
キー比較回数は初期状態に影響されない
•
データ置換回数
) 2 (
1 1 )
2 (
) 1
(N N N 2 N
C = − + − + + = −
− 1
= N
M
単純挿入法
単純挿入法
•
注目している部分列の先頭要素を，
既に整列された部分列の適切な場所に挿入する．
単純挿入法のアルゴリズム
for 𝑖𝑖 ← 2 to 𝑛𝑛 do
if 𝑎𝑎0, … , 𝑎𝑎𝑖𝑖−1
の中に，
𝑎𝑎𝑖𝑖 < 𝑎𝑎𝑗𝑗となる
𝑎𝑎𝑗𝑗が存在する
then条件を満たす最初の
𝑎𝑎𝑗𝑗の直前に
𝑎𝑎𝑖𝑖を挿入する．
end end
実行例
a[] =
７，２，３，４，８，１，５，６
a[] =２，７，３，４，８，１，５，６
a[] =２，３，７，４，８，１，５，６
a[] =２，３，４，７，８，１，５，６
a[] =２，３，４，７，８，１，５，６
a[] =１，２，３，４，７，８，５，６
a[] =１，２，３，４，５，７，８，６
a[] =１，２，３，４，５，６，７，８
単純挿入法の計算量
•
比較回数
𝐶𝐶 ≤ 1 + 2 + ⋯ + 𝑛𝑛 − 1 = 𝑂𝑂 𝑛𝑛2
•
挿入回数
𝑁𝑁 ≤ 𝑛𝑛 − 1
バブルソート法
バブルソート法
基本的な考え方
1.
隣の要素と比較する．
2.
順序が入れ替わっていれば，順序を正す．
バブルソート法
1.i=0～N-2について以下を繰り返す 2.jをN-1とする
3.a[j]とa[j-1]を比較し、a[j]が小さ
ければ交換
4.jを1減らし、j>iのとき3.にもどる
20 4
10 2
23 7 15
12 9
6 4 20
比較 4
10
比較 4 10
交換 10 4 10 44
2
比較 4 22
23
比較 2 23
交換 23 2 23 2
0 1 2 3 4 5 6 7 8 9
12 7 9
6
2 6 9 12 7 15 23 4 10 20
2 15 23 4 10 20
確定 次の検索範囲
バブルソート法の計算量
比較回数
•
配列状態に関わらず同じ
) 2 (
1 2
N N
C = −
バブルソート法の計算量
置換回数
•
正順に並んでいる場合が最小
•
逆順に並んでいる場合が最大
•
平均は
) 2 (
1 2
max N N
M = −
) 4 (
1 2
ave N N
M = −
min = 0 M
