Web教材一覧>
アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)
バブルソートなどに比べて高速な(計算量オーダーが小さい)代表的なソートの方法であるマージソート、クイックソート、シェルソート、ヒープソートについて、基本的な考え方と数値例、プログラムを示します。
アルゴリズム、マージソート、クイックソート、シェルソート、ヒープソート
次のサイズn(=9)の配列aを昇順にソートすることにします。
i 1 2 3 4 5 6 7 8 9
a[i] 30 80 70 10 50 20 40 90 60
基本的なソートの方法は「基本的なソート方法」で示しました。ここでは、高速なソート方法について概要を説明します。
高速とは、計算量のオーダーが小さいことです。
基本的なソート方法でのオーダーは O(n2) であるのに対して、ここで取り扱う方法(シェルソートを除く)では O(nlog2n) です。
配列を単純に2等分した区分にします。それぞれの区分内でソートされていれば、2つの区分をマージ(併合)することにより、全体がソートされます。区分内でソートされていない場合は、それをさらに2等分して、同様な操作を行います。これを繰り返すことにより全体がソートされた小さな区分になります。
次に、それらの小区分を分割したときと逆の順序でマージすることにより、全体がソートされます。
未:まだソートされていない
済:既にソートされている
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
↑ア │30│80│70│10│50│20│40│90│60│
│ └──┴──┴──┴──┴──┴──┴──┴──┴──┘
│ │未
│ ┌────────┴──────────┐
│ ┌──┬──┬──┬──┬──┐ ┌──┬──┬──┬──┐
│イ │30│80│70│10│50│ │20│40│90│60│
└──┴──┴──┴──┴──┘ └──┴──┴──┴──┘
分 │未 │未
割 ┌──┴──────┐ ┌───┴────┐
┌──┬──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐
│ウ │30│80│70│ │10│50│ │20│40│ │90│60│
│ └──┴──┴──┘ └──┴──┘ └──┴──┘ └──┴──┘
│ │未 │済 │済 │未
│ ┌──┴───┐ │ │ ┌─┴──┐
↓ ┌──┬──┐ ┌──┐ │ │ ┌──┐ ┌──┐
エ │30│80│ │70│ │ │ │90│ │60│
↑ └──┴──┘ └──┘ │ │ └──┘ └──┘
│ │済 │済 │ │ │済 │済
│ └──┬───┘ │ │ └─┬──┘
│ ┌──┬──┬──┐ │ │ ┌──┬──┐
オ │30│70│80│ │ │ │60│90│
マ └──┴──┴──┘ │ │ └──┴──┘
l └──┬──────┘ └───┬────┘
ジ ┌──┬──┬──┬──┬──┐ ┌──┬──┬──┬──┐
カ │10│30│50│70│80│ │20│40│60│90│
│ └──┴──┴──┴──┴──┘ └──┴──┴──┴──┘
│ └────────┬──────────┘
│ ┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
↓キ ソート終了│10│20│30│40│50│60│70│80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
手順の説明
ソートの手順は、上図から明白でしょう。ア~エでデータの量を半分ずつに分割していく間に、区分のなかでソートしていれば、その区分はそのままにしておき、ソートされていない区分はさらに半分に分割していきます。
それにより、エの段階で、すべての区分が区分内でソートされました。
次に、分割と逆の順序で2つずつの区分をマージしていきます。オ~キのプロセスにより一つの配列になりました。
ア function merge_sort(left, right) {
イ var i, j , k, mid, w;
ウ work = new Array(11); ──作業領域が必要
エ left = eval(left);
オ right = eval(right);
カ if (left < right) { ──分割して一つの要素になるまで行う
キ if (right-left==1) { ┐
ク if (a[left]>a[right]){ │
ケ w = a[left]; ├左右が単一の要素の場合
コ a[left] = a[right]; │ 左>右ならばスワップ
サ a[right] = w; │
シ } │
ス } ┘
セ else { ──もっと分割できる場合
ソ mid = Math.floor((left+right)/2); ┐
タ merge_sort(left,mid); ├左右2等分して再帰を行う
チ merge_sort(mid+1,right); ┘
ツ i = left; ┐
テ j = mid+1; │
ト k = 1; │
ナ while (i<=mid && j<=right) { ├配列aを作業領域にコピー
ニ if (a[i] < a[j]) work[k++]=a[i++]; │しながら左右をマージする
ヌ else work[k++]=a[j++]; │
ネ } │
ノ while (i<=mid) work[k++]=a[i++]; │
ハ while (j<=right) work[k++]=a[j++]; ┘
ヒ i = left; ┐
フ j = mid+1; │
ヘ k = 1; ├作業領域から配列に戻す
ホ while (i<=mid) a[i++] = work[k++]; │
マ while (j<=right) a[j++] = work[k++]; ┘
ミ }
ム }
メ }
呼び出し側(メインプログラム)では、
merge_sort(1, n);
と指定します。
ソートする配列a、そのサイズnは共通領域で定義されているものとします。
全体のなかから、中間的な基準となる要素を1つ選び(ピボット-枢軸-という)、これより小さい要素と大きい要素の区分に分割します。さらに分割した2つの区分の中で分割を行います。これを繰り返してソートを行う方法です。
ピボットより大の要素を探す ピボットより小の要素を探す
──────→ ▽ ←──────
┌───────────┬──┬───────────┐
│30 80 70 10│50│20 40 90 60│
└───────────┴──┴───────────┘
ア └─────スワップ────┘
┌───────────┬──┬───────────┐
│30 40 70 10│50│20 80 90 60│
└───────────┴──┴───────────┘
イ ▽ └─スワップ──┘ ▽
┌──┬──┬─────┐ ┌──┬──┬─────┐
│30│40│20 10│50│70│80│90 60│
└──┴──┴─────┘ └──┴──┴─────┘
ウ └────┘ └────┘ カ
┌──┬──┬─────┐ ┌──┬──┬─────┐
│30│10│20 40│50│70│60│90 80│
└──┴──┴─────┘ └──┴──┴─────┘
エ └─┘▽ ▽└─┘ キ
┌──┬──┬─────┐ ┌──┬──┐
│10│30│20 40│50│60│70│90 80
└──┴──┴─────┘ └──┴──┘
オ ▽└─┘ ▽ ク
┌──┬──┬─────┐ ┌──┬──┐
│10│20│30 40│50 60 70│90│80│
└──┴──┴─────┘ └──┴──┘
└─┘ ケ
┌──┬──┐
10 20 30 40 50 60 70│80│90│
└──┴──┘
──────── ソートされている ───────→
ア function quick_sort(left, right) {
イ var i, j;
ウ var pivot;
エ var w;
オ left = eval(left);
カ right = eval(right);
キ i = left; /* 対象区分の左端 */
ク j = right; /* 対象区分の右端 */
ケ pivot = a[Math.floor((i+j)/2)]; /* 範囲の中点をピボットにする */
コ while (i < j) {
サ while( a[i] < pivot ) ++i; /* ピボット以上の値が見つかるまで右へ */
シ while( a[j] > pivot ) --j; /* ピボット以下の値が見つかるまで左へ */
ス if ( i < j ) { /* 左>ピボット>右 なのでスワップ */
セ w = a[i];
ソ a[i] = a[j];
タ a[j] = w;
チ }
ツ }
テ if (left < i-1) quick_sort(left, i-1); /* 左側についてクイックソートを再帰 */
ト if (j+1 < right) quick_sort(j+1, right); /* 右側についてクイックソートを再帰 */
ナ }
シェルソートは、ある一定距離だけ離れた要素同士でスワップを行います。それを繰返し、スワップが発生しなくなったら、、この距離を少しずつ縮めて距離が1になるまで行うとソートされています。
距離hのとりかたは多様な考え方がありますが、データ数が比較的小さいときには、h=3k+1<n となる最大値から開始して、3ずつ減らしていく方法が広く行われています。
ア hmax = 3*Math.floor((n-1)/3) + 1;
イ for (h=hmax; h>=1; h=h-3) { ──┐
ウ swap = 1; ├距離の幅h
エ while (swap == 1) { ──┐ │を狭くする
オ swap = 0; │
カ for (i=1; i<=n-h; i++) { ┐ ├hおきで
キ j = i + h; │ │ソートされ
ク if (a[i] > a[j]) { │ │るまで行う
ケ w = a[i]; │ │
コ a[i] = a[j]; │
シ a[j] = w; ├hだけ離れた
ス swap = 1; │要素間で比較
セ } │
ソ } ──┘ │ │
タ } ──┘ │
チ } ──┘
距離h=7
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│30│80│70│10│50│20│40│90│60│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
ア └①─┼─────────────────┘
└②───────────────────┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│30│ │ │ │ │ │ │90│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │60←─────────────────→80│スワップ発生
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│30│60│70│10│50│20│40│90│80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
イ └①─┼─────────────────┘
└②───────────────────┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│30│ │ │ │ │ │ │90│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │60│ │ │ │ │ │ │80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
距離h=4
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│30│60│70│10│50│20│40│90│80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
└①─┼──┼──┼──┘│ │ │ │ │
└②─┼──┼───┼─┘ │ │ │
ウ └③─┼───┼────┘ │ │
└④──┼───────┘ │
└⑤─────────┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│30│ │ │ │50│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │20←────────→60│ │ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │40←────────→70│ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │10│ │ │ │90│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│ │ │ │80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│30│20│40│10│50│60│70│90│80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
└①─┼──┼──┼──┘│ │ │ │ │
└②─┼──┼───┼─┘ │ │ │
エ └③─┼───┼────┘ │ │
└④──┼───────┘ │
└⑤─────────┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│30│ │ │ │50│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │20│ │ │ │60│ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │40│ │ │ │70│ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │10│ │ │ │90│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│ │ │ │80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
距離h=1
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│30│20│40│10│50│60│70│90│80│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
オ └①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│20⇔30│ │ │ │ │ │ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │30│40│ │ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │10⇔40│ │ │ │ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │40│50│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│60│ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑥│ │ │ │ │ │60│70│ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑦│ │ │ │ │ │ │70│90│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑧│ │ │ │ │ │ │ │80⇔90│スワップ発生
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│20│30│10│40│50│60│70│80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
カ └①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│20│30│ │ │ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │10⇔30│ │ │ │ │ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │30│40│ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │40│60│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│60│ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑥│ │ │ │ │ │60│70│ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑦│ │ │ │ │ │ │70│80│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑧│ │ │ │ │ │ │ │80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│20│10│30│40│50│60│70│80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
キ └①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│10⇔20│ │ │ │ │ │ │ │スワップ発生
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │20│30│ │ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │30│40│ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │40│50│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│60│ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑥│ │ │ │ │ │60│70│ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑦│ │ │ │ │ │ │70│80│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑧│ │ │ │ │ │ │ │80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│10│20│30│40│50│60│80│80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
ク └①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
①│10│20│ │ │ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
②│ │20│30│ │ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
③│ │ │30│40│ │ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
④│ │ │ │40│50│ │ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑤│ │ │ │ │50│60│ │ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑥│ │ │ │ │ │60│70│ │ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑦│ │ │ │ │ │ │70│80│ │
├──┼──┼──┼──┼──┼──┼──┼──┼──┤
⑧│ │ │ │ │ │ │ │80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
終了
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│10│20│30│40│50│60│80│80│90│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
距離hを3k+1のルールにより、h=7、4、1の順で行いました。
アではh=7です。①で、a[1]=30 と a[1+7]=a[8]=90 の比較をしますが、a[1]<a[8] なので、そのままになります。②で、a[2]=80 と a[9]=60 の比較をしますが、a[2]>a[9] なので、スワップします。
スワップが行われたので、h=7を繰り返すためイを行います。イではスワップが行われなかったので、距離hを狭くしてh=4とし、ウを行います。
このような手順により、h=1でスワップが行われなくなった(ク)でソートが終了します。
ヒープソートとは、配列から2分木を作り、それを 親<左の子<右の子 の順序木にするように修正することにより、ソートする方法です。
2分木を作成する
ア for (k=n; k>=1; k--) { ──葉のほうからデータを割り付ける
イ i = k; i、jはノード番号
ウ w = a[i]; (親=i、左の子=j、右の子=j+1)
エ while ((j = i*2) <= n) { ──┐
オ if ((j<=n-1) && (a[j] < a[j+1])) j++; ├親になる(葉ではない)
カ if ( w >= a[j]) break; │ノードのとき
キ a[i] = a[j]; │ 親>子になるように
ク i = j; │ 必要ならばスワップ
ケ } ──┘
コ a[i] = w; ──ノードが葉のときは、ノード番号=要素番号として入れる
サ } 葉ではないときは、上のスワップにより得た親のノードに入れる
親<左の子<右の子 になるように修正する
シ k = n;
ス while (k >= 2) {
セ w = a[k];
ソ a[k] = a[1]; ──a[1]=ルート(本来ならば最小値)
タ k--; ──⑨→⑧→…降順で行う
チ i = 1;
ツ while ((j=i*2) <= k) { ──┐
テ if ((j < k) && (a[j] < a[j+1])) j++; │
ト if (w >= a[j]) break; │
ナ a[i] = a[j]; ├数値例での解説参照
ニ i = j; │
ヌ } │
ネ a[i] = w; ──┘
ノ }