プログラミング演習Ⅲ- Sorting Quick Sort and Merge Sort P. Ravindra S. De Silva e-Mail: ravi@cs.tut.ac.jp, Room F-413 URL: www.icd.cs.tut.ac.jp/~ravi/prog3/index_j.html 1

クイックソート

クイックソート クイックソートは配列中の適当な値（これをピボットと呼ぶ；データ総数の中央値が望ましい）を使用して、この基準値より大きいか小さいかによって二分割しながら並び変えてゆくアルゴリズム 分割: 適当な配列要素 p を ピボット として選択する　例, 一番目の配列要素 残りの要素を次のように配分する FirstPart, 　　　< p　（p未満の値をもつ要素） SecondPart, 　≥ p　（p以上の値をもつ要素） FirstPart と SecondPart を 再帰的に並び変える 結合: ソートが適切に終了するまで何もしなくてよい

p p p >= x x < p x < p p p >= x A: ピボット 分配 再帰呼び出し クイックソート FirstPart SecondPart p p >= x x < p 再帰呼び出し x < p p p >= x ソート済 FirstPart SecondPart ソート済

クイックソート Quick-Sort(A, left, right) if left ≥ right return else middle ← Partition(A, left, right) Quick-Sort(A, left, middle–1 ) Quick-Sort(A, middle+1, right) end if

Partition(A, left, right) x ← A[left] i ← left for j ← left+1 to right if A[j] < x then i ← i + 1 swap(A[i], A[j]) end if end for j swap(A[i], A[left]) return i

分配の例 i=0 A: 4 8 6 3 5 1 7 2 j=1

分配の例 i=0 A: 4 8 8 6 3 5 1 7 2 j=1

分配の例 i=0 A: 4 8 6 6 3 5 1 7 2 j=2

分配の例 i=1 i=0 A: 4 8 3 8 6 3 3 5 1 7 2 j=3

分配の例 i=1 A: 4 3 6 8 5 5 1 7 2 j=4

分配の例 i=1 A: 4 3 6 8 5 1 1 7 2 j=5

分配の例 i=2 A: 4 3 6 1 6 8 5 1 7 2 j=5

分配の例 i=2 A: 4 3 1 8 5 6 7 7 2 j=6

分配の例 i=2 i=3 A: 4 3 1 8 2 5 6 7 8 2 2 j=7

分配の例 i=3 A: 4 3 1 2 5 6 7 8 j=8

分配の例 i=3 A: 4 2 3 1 2 4 5 6 7 8

分配の例 適切な位置に ピボットが配置された A: 2 3 1 4 5 6 7 8 x < 4 4 >= x

Quick-Sort(A, 0, 7) Partition A: 4 8 6 3 5 1 7 2 2 3 1 5 6 7 8 4

Quick-Sort(A, 0, 7) Quick-Sort(A, 0, 2) , partition A: 4 5 6 7 8 2 3 1 5 6 7 8 2 3 1 2 1 3

Quick-Sort(A, 0, 7) Quick-Sort(A, 0, 0) , return , base case 4 5 6 7 8 5 6 7 8 1 2 3 1

Quick-Sort(A, 0, 7) Quick-Sort(A, 1, 1) , base case 4 5 6 7 8 1 2 3

Quick-Sort(A, 0, 7) Quick-Sort(A, 0, 2), return 1 3 4 5 6 7 8 2 1 3

Quick-Sort(A, 0, 7) Quick-Sort(A, 4, 7) Quick-Sort(A, 2, 2), return , partition 2 1 3 4 5 6 7 8 6 7 8 5

Quick-Sort(A, 0, 7) Quick-Sort(A, 5, 7) , partition 2 1 3 4 5 6 7 8 6 6 7 8 6 7 8 6

Quick-Sort(A, 0, 7) Quick-Sort(A, 6, 7) , partition 2 1 3 4 5 6 7 8 7 7 8 7 8

Quick-Sort(A, 0, 7) Quick-Sort(A, 7, 7) , base case , return 2 1 3 4 5 6 7 8 8

Quick-Sort(A, 0, 7) Quick-Sort(A, 6, 7) , return 2 1 3 4 5 6 7 8

Quick-Sort(A, 0, 7) Quick-Sort(A, 5, 7) , return 2 1 3 4 5 6 8 7

Quick-Sort(A, 0, 7) Quick-Sort(A, 4, 7) , return 2 1 3 4 5 6 8 7

Quick-Sort(A, 0, 7) Quick-Sort(A, 0, 7) , done! 2 1 3 4 5 6 8 7

マージソート

A ソート完了! マージソートの概念 二分割する 再帰的に 並び変える マージ（合併） FirstPart SecondPart

A: 結合 配分の仕方 A[middle] A[left] ソート済 FirstPart ソート済 SecondPart A[right] 均衡のとれた配分を達成したい データをAとBに二等分する 再帰的にAとBをソートする 二つの配列を一つに結合するmerge処理を呼び出して、AとBの配列を結合する A[middle] A[left] ソート済 FirstPart ソート済 SecondPart A[right] 結合 A: ソート済

Merge-Sort (A, left, right) if left ≥ right return else マージソート: アルゴリズム Merge-Sort (A, left, right) if left ≥ right return else middle ← b(left+right)/2 Merge-Sort(A, left, middle) Merge-Sort(A, middle+1, right) Merge(A, left, middle, right) 再帰呼び出し

Example n/2のサイズでリストを分割する [10, 4, 6, 3, 8, 2, 5, 7] [10, 4, 6, 3] [8, 2, 5, 7] [10, 4] [6, 3] [8, 2] [5, 7] [4] [10] [3][6] [2][8] [5][7]

Example Cont’d 結合 [2, 3, 4, 5, 6, 7, 8, 10 ] [3, 4, 6, 10] [2, 5, 7, 8] [4, 10] [3, 6] [2, 8] [5, 7] [4] [10] [3][6] [2][8] [5][7]

マージソート: 結合例 A: 2 3 7 8 5 15 28 30 6 10 14 1 4 5 6 6 10 14 22 3 5 15 28 L: R: 一時的な保存に用意した配列要素 P. E. S. S. De Silva 8470013681

マージソート: 結合例 A: 1 3 5 15 28 30 6 10 14 k=0 L: R: 3 2 15 3 7 28 8 30 6 1 4 10 14 5 22 6 i=0 j=0

マージソート: 結合例 A: 1 2 5 15 28 30 6 10 14 k=1 L: R: 3 2 5 3 7 15 8 28 1 6 4 10 14 5 22 6 i=0 j=1

マージソート: 結合例 A: 1 2 15 3 28 30 6 10 14 k=2 L: R: 2 3 7 8 6 1 4 10 5 14 22 6 i=1 j=1

マージソート: 結合例 A: 1 2 3 4 6 10 14 k=3 L: R: 2 3 7 8 6 1 10 4 14 5 22 6 i=2 j=1

マージソート: 結合例 A: 1 2 3 4 5 6 10 14 k=4 L: R: 2 3 7 8 1 6 10 4 14 5 22 6 i=2 j=2

マージソート: 結合例 A: 1 2 3 4 5 6 6 10 14 k=5 L: R: 2 3 7 8 6 1 10 4 5 14 6 22 i=2 j=3

マージソート: 結合例 A: 1 2 3 4 5 6 7 14 k=6 L: R: 2 3 7 8 6 1 10 4 14 5 6 22 i=2 j=4

マージソート: 結合例 A: 1 2 3 4 5 6 7 8 14 k=7 L: R: 2 3 3 5 7 15 8 28 1 6 10 4 14 5 22 6 i=3 j=4

マージソート: 結合例 A: 1 2 3 4 5 6 7 8 k=8 L: R: 2 3 3 5 7 15 8 28 6 1 4 10 14 5 6 22 j=4 i=4

Merge(A, left, middle, right) n1 ← middle – left + 1 n2 ← right – middle create array L[n1], R[n2] for i ← 0 to n1-1 do L[i] ← A[left +i] for j ← 0 to n2-1 do R[j] ← A[middle+j] k ← i ← j ← 0 while i < n1 & j < n2 if L[i] < R[j] A[k++] ← L[i++] else A[k++] ← R[j++] while i < n1 while j < n2