情報工学概論 (アルゴリズムとデータ構造) 第2回

実習用環境 C言語 Fortran 90 学習用Ｃ言語開発環境http://9cguide.appspot.com/ Self-extracting Windows x86 http://www.g95.org/downloads.shtml http://ftp.g95.org/g95-MinGW.exe

アルゴリズムの設計 挿入ソート: 逐次添加法 (incremental approach) 分割統治法 (divide-and-conquer) に基づく方法 →マージソート 実行時間の解析が容易であることが多い

分割統治法 問題の再帰的な (recursive) 構造を利用 マージソートでは 分割：問題をいくつかの小さな部分問題に分割 統治：各部分問題を再帰的に解く 統合：それらの解を組合わせて元の問題の解を構成 マージソートでは 分割： n 要素の列を n/2 要素の2つの部分列に分割 統治：マージソートを用いて2つの部分列をソート 統合：2つのソートされた部分列を統合して答を得る

マージソート void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート { int q; if (p < r) { // p==r ならソートする必要なし q = (p+r)/2; MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合 }

1 2 2 3 4 5 6 6 マージ 2 4 5 6 1 2 3 6 マージ マージ 2 5 4 6 1 3 2 6 マージ マージ マージ マージ 5 2 4 6 1 3 2 6

マージ 一時的な配列 B[0,n-1] を用いる void MERGE(data *A, int p, int q, int r, data *B) { // ソートされた部分列 A[p..q] と A[q+1..r] を統合 int i,j,k; data t; k = p; i = p; j = q+1; while (k <= r) { if (j > r) t = A[i++]; // 前半のみにデータがある else if (i > q) t = A[j++]; // 後半のみにデータがある else if (A[i] <= A[j]) t = A[i++]; // 前半のほうが小さい else t = A[j++]; // 後半のほうが小さい B[k++] = t; // 一時的な配列に保存 } for (i=p; i<=r; i++) A[i] = B[i]; // 元の配列に書き戻す

void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート { int q; if (p < r) { // p==r ならソートする必要なし q = (p+r)/2; MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合 } int main(int argc, char *argv[]) data A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}; data B[14]; int i,n; n = 14; MERGE_SORT(A,0,n-1,B); for (i=0;i<n;i++) printf("%d ",A[i]); printf("\n");

Rubyの場合 def merge(a, b) def merge_sort(a) x = [] n = a.length i = 0 j = 0 while i < a.length do if j == b.length then x << a[i] i = i + 1 elsif a[i] < b[j] then else x << b[j] j = j + 1 end x.concat(b[j..-1]) return x def merge_sort(a) n = a.length if n == 1 then return [a[0]] else return merge(merge_sort(a[0..n/2-1]), merge_sort(a[n/2..-1])) end a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0] b = merge_sort(a) p b

Fortran 90の場合 subroutine merge(a, p, q, r, b) program main integer a(:), b(:) integer p, r, q, i, j, k integer t k = p; i = p; j = q+1 do if (.not. (k <= r)) exit if (j > r) then t = a(i); i = i+1 else if (i > q) then t = a(j); j = j+1 else if (a(i) <= a(j)) then else end if b(k) = t; k = k+1 end do do i = p, r a(i) = b(i) end subroutine merge end program main program main integer a(14) integer b(size(a)) a = (/ 27,17,3,16,13,10,1,5,7,12,4,8,9,0 /) print *, "a = ", a print *, "merge sort" call mergesort(a, lbound(a,1), ubound(a,1), b) contains recursive subroutine mergesort(a, p, r, b) integer a(:), b(:) integer p, r integer q if (p < r) then q = (p+r)/2 call mergesort(a, p, q, b) call mergesort(a, q+1, r, b) call merge(a, p, q, r, b) end if end subroutine mergesort

分割統治アルゴリズムの解析 全体の実行時間は問題のサイズに関する漸化式 (recurrence) で記述できることが多い サイズ n の問題に関する実行時間を T(n) とする n  c (ある定数) ならば定数時間((1)) 問題を a 個の部分問題に分割し, それぞれが元のサイズの 1/b 倍になったとすると D(n), C(n): 問題の分割, 統合にかかる時間

マージソートの解析 T(n)= (n lg n) となる n は2のべき乗と仮定する n=1のとき T(n) = (1) 分割： D(n) = (1) 統治：再帰的にサイズn/2の部分問題を解く 2T(n/2) 統合：MERGEは C(n) = (n) T(n)= (n lg n) となる

アルゴリズムの重要性 コンピュータが速くても, 実行時間のオーダが大きいアルゴリズムは役に立たない スーパーコンピュータで挿入ソートを実行 1秒間に1億命令実行 2n2 命令必要 パーソナルコンピュータでマージソートを実行 1秒間に100万命令実行 50 n lg n 命令必要

100万個の数の配列のソート ス－パーコンピュータで挿入ソート パーソナルコンピュータでマージソート オーダの低いアルゴリズムの開発が重要

今までのソーティングアルゴリズム 挿入ソート： (n2) 時間だが，入力サイズが小さいときには高速．in-place マージソート： (n lg n) 時間だが，実行には一時的な配列が必要

新しいソーティングアルゴリズム ヒープソート： (n lg n) 時間, in-place. クイックソート： 最悪 (n2) 時間だが平均実行時間は(n lg n)．実際上は高速．in-place.

クイックソート n 個の数に対して最悪実行時間(n2)のソーティングアルゴリズム 平均実行時間は(n log n) 記法に隠された定数も小さい in-place (一時的な配列が必要ない)

クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング 部分問題への分割: 部分問題の解決 (統治): 配列 A[p..r] を2つの部分配列 A[p..q] と A[q+1..r] に再配置する． A[p..q] のどの要素も A[q+1..r] の要素以下にする． 添字 q はこの分割手続きの中で計算する． 部分問題の解決 (統治): 部分配列 A[p..q] と A[q+1..r] を再帰的にソート 部分問題の統合 A[p..r] はすでにソートされているので何もしない

クイックソートのコード void QUICKSORT(data *A, int p, int r) { int q; if (p < r) { q = PARTITION(A,p,r); QUICKSORT(A,p,q); QUICKSORT(A,q+1,r); } main() QUICKSORT(A,0,n-1);

Rubyの場合 def quick_sort(a) n = a.length if n <= 1 then return a else pivot = a[0] less = a.select{|x| x < pivot} equal = a.select{|x| x == pivot} greater = a.select{|x| x > pivot} return quick_sort(less) + equal + quick_sort(greater) end a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0] b = quick_sort(a) p b Rubyの場合 注：これはin-placeではない （一時的に余分な記憶領域が必要）

配列の分割 int PARTITION(data *A, int p, int r) // O(n) 時間 { int q, i, j; data x, tmp; x = A[p]; i = p-1; j = r+1; while (1) { do {j = j-1;} while (A[j] > x); do {i = i+1;} while (A[i] < x); if (i < j) { tmp = A[i]; A[i] = A[j]; A[j] = tmp; } else { return j; }

A[p..r] 初期状態： i と j は配列の範囲外 x = A[p] = 5 によって分割 x: 枢軸 (pivot) と呼ぶ 5 3 2 6 4 1 3 7 i j A[i]  x A[j]  x となる最初の i, j 7 は正しい分割位置にある 5 3 2 6 4 1 3 7 i j A[i] と A[j] を交換 正しい分割位置になる 3 3 2 6 4 1 5 7 i j

A[i]  x A[j]  x となる最初の i, j 3 3 2 6 4 1 5 7 i j 3 3 2 1 4 6 5 7 A[i] と A[j] を交換 i j i  j となったので q = j を返す A[p..q] は x 以下 A[q+1..r] は x 以上 3 3 2 1 4 6 5 7 j i

Fortran 90の場合 function partition(a, p, r) integer a(:) integer p, r, q, i, j integer x, tmp x = a(p) i = p-1; j = r+1 do j = j-1 if (.not. (a(j) > x)) exit end do i = i+1 if (.not. (a(i) < x)) exit if (i < j) then tmp = a(i); a(i) = a(j); a(j) = tmp else partition = j exit end if end function end program main program main integer a(14) a = (/ 27,17,3,16,13,10,1,5,7,12,4,8,9,0 /) print *, "a = ", a print *, "quick sort" call quicksort(a, lbound(a,1), ubound(a,1)) contains recursive subroutine quicksort(a, p, r) integer a(:) integer p, r, q if (p < r) then q = partition(a,p,r) call quicksort(a,p,q) call quicksort(a,q+1,r) end if end subroutine quicksort

PARTITIONの正当性 PARTITIONの返り値を q とする A[p..r] の分割後に満たされるべき条件 A[p..q] はある pivot x 以下 A[q+1..r] は x 以上 p  q < r q = r となると，QUICKSORTは停止しないため，どんな A に対しても q < r となることを保障する必要がある

do {j = j-1;} while (A[j] > x); 初期状態は i < j do {j = j-1;} while (A[j] > x); 　 do {i = i+1;} while (A[i] < x);　の終了後 p  i, j  r A[j+1..r] は x 以上 A[p..i-1] は x 以下 A[i]  x  A[j] i < j のとき，A[i] と A[j] を交換すると A[j..r] は x 以上 A[p..i] は x 以下 i  j のとき q = j

PARTITIONの終了時に q = j = r とする while (1) のループを実行する毎に j は1以上減る 終了時に j = r ならばこのループは1度しか実行されていない しかし1回目のループでは x = A[p] なので i = p PARTITIONは p < r の場合のみ呼ばれるので，1回目のループでは p = i < j = r つまり1回目のループでは終了しない よってPARTITION終了時に q = r とはならない．つまり q < r

8.2 クイックソートの性能 クイックソートの実行時間は分割が平均化されているかどうかに依存 これはpivotの選択に依存 分割が平均化されていれば実行時間は漸近的にマージソートと同じ ((n log n)) 最悪時は (n2)

最悪の分割 最悪の場合は，PARTITIONによって領域が 1 要素と n-1 要素に分けられる場合 分割には (n) 時間かかる 実行時間に対する漸化式は T(n) = T(n1) + (n), T(1) = (1) T(n) = (n2) 最悪実行時間は挿入ソートと同じ 入力が完全にソートされているときに起こる (挿入ソートなら O(n) 時間)

再帰木

最良の分割 クイックソートが最も速く動作するのは，PARTITIONによってサイズ n/2 の2つの領域に分割されるとき. T(n) = 2T(n/2) + (n) T(n) = (n lg n) ちょうど半分に分割される場合が最速

平衡分割 PARTITIONで常に 9 対 1 の比で分割されると仮定する T(n) = T(9n/10) + T(n/10) + (n) 再帰の深さは 漸近的には中央で分割するのと同じ 分割の比が 99 対 1 でも同じ (定数比なら良い)