選択ソート挿入ソート

選択ソート
挿入ソート
アルゴリズム論第3回講義
４要素の選択ソート
２
a(0)
４
a(1)
１
a(2)
３
a(3)
２
a(0)
1
４
a(1)
4
１
a(2)
2
３
a(3)
3
1
a(0)
4
a(1)
2
a(2)
3
a(3)
1
a(0)
決
定
4
a(1)
2
a(2)
3
a(3)
start
a(0)a(1)………………a(9)
10個のデータのソート
低速版選択ソート
のフローチャート
前処理
（初期化）
n=10
i=0
yes
i>=n-1
stop
no
j=i+1
外部ループ
内部ループ
j>n-1
no
データ
交換
j++
i++
yes
(データ交換）
if a(i) =< a(j) then go to j++
no b=a(j), a(j)=a(i), a(i) =b
j++
（左端に最小値を
常に保存する方法）
ｊのインクリメンタル
比較対象となる配列要素を
右に一つ移動する
iのインクリメンタル
最小値が左端に来たので，
基準となる配列要素を右
に一つ移動する
選択ソート
ハンドシミュレーション
21
35
11
80
54
１回目の処理結果？ a(0) a(2)交換
11,35,21,80,54
２回目の処理結果？ a1 a2 交換
11,21,35,80,54
３回目の処理結果？交換なし
11,21,35,80,54
４回目の処理結果？ a3 a4 交換
11,21,35,54,80
標準版選択ソートのアルゴリズム
低速版選択ソート
→左端に最小値を常に保存するため交換回数
が多い
標準版選択ソート
→1回のスキャンで最小値を保存する配列要素
の添え字を記録
→スキャン終了後に左端と最小値を保存する配
列要素を交換すればデータ交換は1回ですむ
start
a(0)a(1)………………a(9)
前処理
（初期化）
n=10
i=0
10個のデータのソート
標準版選択ソート
のフローチャート
yes
i>=n-1
stop
no
suffixmin=i, j=i+1
外部ループ
j>n-1
内部ループ
yes
no
最小値探索
添え字保存
j++
b=a(suffixmin)
a(suffixmin)=a(i)
a(i)=b
i++
①(最小値探索，添え字保存）
if a(suffixmin) =< a(j) then go
to j++
no suffixmin=j
j++
ｊのインクリメンタル
比較対象となる配列要素を
右に一つ移動する
iのインクリメンタル
最小値が左端に来たので，
基準となる配列要素を右
に一つ移動する
選択ソート
• バブルソート：
隣同士を比較．最悪毎回入替え
• 選択ソート：
１パスで最小値を見つけて(選択して）
最小値と左端を交換する（交換は1回だけ）．
N個のデータの選択ソート
比較
交換
最大
(N-1)+(N-2)+…+1
=1/2N(N-1)=1/2(N2-N)
2
O(N )
(N-1)
O(N )
平均
(N-1)+(N-2)+…+1
=1/2N(N-1)=1/2(N2-N)
2
O(N )
½(N-1)
O(N )
最小
(N-1)+(N-2)+…+1
=1/2N(N-1)=1/2(N2-N)
2
O(N )
0
（ビッグオーではなく零）
挿入ソート
現実的には，既にソート済みのデータがあり，
そこにデータが追加されソートしたいケースが多くある．
バブルソートや選択ソートを使って一からソートするか？
遅くて非現実的．そこで挿入ソートの出番となる
１，３，５，８，９，１４，２５，３５，６７，８９，９７
２４，４５，４６，６８，７７
挿入ソート
• 挿入⇒部分ソート（一部ソート済みのデータ）
に未ソートのデータを挿入する
（小）ソート済み（大）
未ソート（バラバラ)
マーク
• バブルソートや選択ソートより通常は高速
• 一部ソート済みのデータがある時に威力を発揮する
挿入ソートのイメージ
20
31
50
54
43
20
31
50
43
54
20
31
43
50
54
20
31
43
50
54
逆順なので交換
逆順なので交換
順序通りなので停止
確定
（低速版）挿入ソートのフローチャート
a(1)が最初の
マーク位置
マークが右端まで到達？
<が正しい
マークをjに保存
Jが左端まで到達？
>が正しい
隣接比較
>が正しい正順ならそのまま
逆順なら交換
隣接比較を左へシフト
マークを右へシフト
本流れ図には
まだ誤りがある！
問題：N個のデータの挿入ソートの計算量を求めよ
（乱れが少ないデータには高速）
比較
最大
平均
最小
交換

Download Report