第4回講義ノート

アルゴリズムと情報処理
（第４回）
慶應義塾大学生命情報学科
榊原康文
ソートアルゴリズムの演習

今まで勉強した３つのソートのアルゴリズムを使って，具体的
なソートの問題を解いてみる
① １６個と８個のランダムに並んだ整数列の演習問題
 １６個の整数列に対して，マージソートとクイックソートを使って解く
 ８個の整数列に対して，ヒープソートを使って解く
 演習問題のデータは，全員異なる整数列が配られる
② それぞれのソートアルゴリズムの計算過程を解答用紙に記
入しながら，ソートの演習問題を解く
③ ３つの演習問題が完了したら，解答用紙に氏名と学籍番号
を記入して提出する
④ すべての演習問題は，授業時間中に終わらせる
マージソート（復習）

マージとは：
–
１
１
与えられた2つのソート済みの配列 A[1],...,A[m] と
B[1],...,B[n] から，これらを統合した1つのソートされた
配列 C[1],..., C[m+n] を作る手続き
２
２
３
３
４
５
５
６
６
８
１
１
２
３
３
８
４
１０
１
２
２
５
３
６
４
１５
７
８
１０１５
マージソート（復習）

マージソート：
①
入力配列： A[1],...,A[n] が与えられる
②
n2k と仮定する（長さ n が2の巾乗になっている）
（そうでない場合は，高々 n1 個までのダミー要素（値は∞）を付加えて２
の巾乗にする）
１
７
２３４
２１０１
５
６
＋
６７８
∞ ∞ ∞
③
入力配列をk回分割することで要素一つだけからなる部分配列がn個
できる
④
2つの配列を次々にマージしていく
⑤
この操作を繰り返してk回行うと最終的に長さn2kのソートされた配列
が最終的に得られる
マージソート
解答として
この図を示す
（誤り）
14, 18, 21, 37
クイックソートプログラム
（復習）
procedure Q-SORT(A, p, q)
begin
if p < q then ;
r := PARTITION(A, p, q) ;
Q-SORT(A, p, r) ;
Q-SORT(A, r+1, q) ;
end
procedure PARTITION(A, p, q)
var i, j , a ;
begin i := p ; j := q ;
a を A[p, q] の中から適当に選んでくる ;
while i ≦ j do ;
while A[i] < a do i := i + 1 ;
while A[j] ≧ a do j := j  1 ;
if i ≦ j then;
A[i] と A[j] を交換する ;
i := i + 1 ; j := j  1 ;
r := i  1 ;
end
クイックソート（復習）
PARTITION(A, p, q) ：

①
枢軸要素（pivot） : A[r+1..q]の要素の最小値 a （すなわち，2つの分割
を定める境界となる値）
–
枢軸要素の選択の方法：

配列要素を左から見ていって異なる最初の値の大きい方をとる
（配列の左端の要素の値をとる，の改良版）
–

ランダムに1つ選ぶ

ランダムに3つの値を選びその中央値をとる
（例題）
A[1]
A[10]
3
2
0
5
8
3
4
1
3
2
2
2
0
1
8
3
4
5
3
3
≧３
＜３
PARTITIONの実行例
枢軸要素＝３
枢軸要素＝３
A[1]
3
(a) 開始
2
0
5
8
3
4
A[10]
1
3
2
i
(b) ３と２を交換
j
3
2
0
2
8
3
4
1
2
0
5
8
3
4
i
i>j より終了
2
2
0
1
8
j i
3
4
出会いと終了
2
j
1
２回目の交換地点
(d) i=5, j=4となり，
3
最初の交換地点
i
(c) ５と１を交換
5
3
3
3
3
j
5
クイックソートの実行例
Q-SORT(A, 1, 10)
解答として
この図を示す
Q-SORT(A, 5, 10)
r := 4
Q-SORT(A, 1, 4)
r := 2
Q-SORT(A, 1, 2)
r := 1
Q-SORT(A, 3, 4)
Q-SORT(A, 1, 1) となり，
条件 p=1<q=1 は成り立た
ないので，何もせずに
returnとなる
データ構造：ヒープ（復習）
6
9
3
２つの子供
5
高さ = log n
親ノードの要素
≦
ノード（節点）
8
15 13
子ノードの要素
20
23
（高さ）ー１までは，
25
完全２分木
10 30
ノードの増加順番：
1
1
2
1
1
2
2
3
4
1
3
2
4
3
5
ヒープソート（復習）
 ヒープソート：
① 空のヒープを用意する
② 要素 A[1],...,A[n]の順にINSERTを用いて n 個の要素から
なるヒープを作る
③ DELETE_MINを n 回用いて要素を小さい順に取り出して
整列させる
④ 二つの操作に要する手間は，おのおの１回ごとにO(log n)
であったから，整列に要する時間はO(n log n)となる
ヒープ上の操作①： DELETE_MIN
DELETE_MIN：

A上の順序に関して，最小の要素をAから削除する
–
ヒープの性質から，根には最小の要素が貯えられているので，根に
対応する配列上のA[1]を削除すればよい
–
これだけでは他の残された木がヒープの性質をみたさないので以下
の修正を行う：
①
木の（最も深い）葉のうちで最も右にあるもの（配列上では最後の
要素）を新しい根として移動する
②
二つの子の小さい方と比較して親の方（の要素が順序の上で）が
大きければその子と交換する
③
この操作を根から葉へ下向きに交換の必要がなくなるまで繰り返
す
④
この操作はヒープの高さに比例する時間Θ(log
n) で実行できる
ヒープ上の操作①： DELETE_MIN
ヒープ上の操作②： INSERT
INSERT：

Aに要素xを挿入する
–
要素 x を挿入後は，Aはヒープの性質を保つ必要がある：
①
今あるヒープの（最も深い葉のうちで）最右の葉のすぐ右隣の位
置へ（要素 x ）おく
②
もし（今ある）ヒープが完全２分木ならば，最左の葉の左の子とし
て登録する
③
（挿入された要素 x の）その親と比較し，親の方が大きい限り
次々と交換していく
④
この操作を根から葉へ下向きに交換の必要がなくなるまで繰り返
す
⑤
この操作はヒープの高さに比例する時間Θ(log
n) で実行できる
ヒープ上の操作②： INSERT
ヒープソート
解答としてこの図を示す
入力列 (8, 4, 9, 3, 7)
8
8
4
4
8
4
4
8
8
9
3
3
4
8
3
9
4
8
9
7
9
ヒープソート
解答としてこの図を示す
入力列 (8, 4, 9, 3, 7)
（１）入力要素列に
対するヒープ
の作成
（２）最小要素の
取り出し

Download Report