JavaScript によるソートアルゴリズムの可視化
こちらのつづきです。
これで最終回です。
プログラムの解説 - ソートアルゴリズム（２／２）
algorithms.js で、クイックソートとマージソートの実装です。
これらは平均計算量が $O(n\ log\ n)$ のシリーズです。
このへんは処理の様子がちょっと分かりづらいので、
main.js 側から呼び出すときにデータを多めに渡すことで
俯瞰できるようにしてあります。
QuickSort クラス
クイックソートを実装します。
データから適当な値を取り出して（※）、
それより小さいもの／大きいものに選り分ける、を繰り返して
ソートを完了させていきます。
※この値の取り方は計算量に関わる重要ポイントですが、
今回は、渡された区間の真ん中を取るだけにしています。
/**
* クイックソート O(n log n)
*/
class QuickSort extends VisualizedAlgorithm {
*generator ( ) {
const len = this.arr.length;
yield* this.partition( this.arr, 0, len - 1 );
return this.resultProperties();
}
*partition ( arr, left, right ) {
const pivot_index = Math.floor( ( left + right ) / 2 );
const pivot = arr[pivot_index];
let [i, j] = [left, right];
for ( ;; ) {
while ( arr[i] < pivot ) {
i++;
this.loops++;
}
while ( pivot < arr[j] ) {
j--;
this.loops++;
}
yield this.yieldProperties( pivot_index, i, j );
if ( i >= j ) {
break;
} else {
if ( arr[i] !== arr[j] ) {
[arr[i], arr[j]] = [arr[j], arr[i]];
this.swaps++;
}
i++;
j--;
}
}
if ( left < i - 1 ) {
yield* this.partition( arr, left, i - 1 );
}
if ( j + 1 < right ) {
yield* this.partition( arr, j + 1, right );
}
}
}
*generator () // QuickSort
前回分のジェネレータと比較すると中身が少なく見えますが、
ここで大事なのは以下の部分です。
yield* this.partition( this.arr, 0, len - 1 );
こちらは、partition メソッドへ処理を委任する、というものです。
理由についてはそちらのメソッドの方で解説します。
yield* が、別のジェネレータへの委任 をあらわしています。
*partition ( arr, left, right )
クイックソートというアルゴリズムの肝にあたる部分です。
さきほどの generator メソッドからジェネレータを委任したのは、
このメソッドで再帰をしたかったからです。
partition は、引数の配列を左右に分けていきます。
具体的には、呼び出されたときに pivot を選定したあと、
データの先頭（左）から pivot より大きいもの、
データの末尾（右）から pivot より小さいもの、を
順番に取り出し、それらを入れ替えていきます。
この動作で、左右からの探索が交差した時点の位置から見ると、
左側（pivot より小さい） ／ 右側（pivot より大きい）に
選り分けられた状態となります。
このようにして分割ができたところで、
左右の配列をそれぞれ partition (=自分自身) に渡して、
さらなる大小の選り分けによる分割を進めていきます。
最終的に pivot との大小比較・入れ替えが発生しなくなる、
つまりソート済みでない要素がなくなるまで繰り返せば、
ソートが完了した状態を実現することができます。
赤が partition により pivot とした値で、
青が探索中の左側（pivot より大きい）、
緑が探索中の右側（pivot より小さい）をあらわし、
青と緑が入れ替わっていきます。
次に赤が動いた瞬間が、分割後の再帰呼び出しの始まりであり、
引き続き青と緑の入れ替えによってソートが進んでいきます。
MergeSort クラス
マージソートを実装します。
データの分割と、分割した配列の併合 (マージ) を繰り返して、
ソートを実現するものです。
このマージの際に、小さい（あるいは大きい）ほうを取り出す、
というルールを設けることで、結果的にソートされる仕組みです。
/**
* マージソート O(n log n)
*/
class MergeSort extends VisualizedAlgorithm {
*generator ( ) {
const len = this.arr.length;
yield* this.mergesort( this.arr, 0, len );
return this.resultProperties();
}
*mergesort ( arr, left, right ) {
const _arr = [];
if ( left >= right - 1 ) {
_arr.push( arr[left] );
} else if ( left == right - 2 ) {
if ( arr[left] < arr[right - 1] ) {
_arr.push( arr[left], arr[right - 1] );
} else {
_arr.push( arr[right - 1], arr[left] );
this.swaps++;
}
} else {
const mid = Math.floor( ( left + right ) / 2 );
const leftArr = yield* this.mergesort( arr, left, mid );
const rightArr = yield* this.mergesort( arr, mid, right );
for ( let [i, j] = [0, 0]; ; ) {
if ( leftArr[i] < rightArr[j] ) {
_arr.push( leftArr[i] );
arr[left + i + j] = leftArr[i];
i++;
} else {
_arr.push( rightArr[j] );
arr[left + i + j] = rightArr[j];
j++;
this.swaps++;
}
yield this.yieldProperties( left + i + j - 1, left + i, mid + j );
if ( i >= leftArr.length || j >= rightArr.length ) {
_arr.push( ...rightArr.slice( j ) );
_arr.push( ...leftArr.slice( i ) );
_arr.forEach( ( value, index ) => arr[left + index] = value );
break;
}
this.loops++;
}
}
return _arr;
}
}
*generator () // MergeSort
構造的にはクイックソートと同様で、
こちらも大事なのは以下の部分です。
yield* this.mergesort( this.arr, 0, len );
詳しくはそちらのメソッドで解説します。
*mergesort ( arr, left, right )
名前のとおりマージソートを実現するメソッドで、
こちらも再帰的に呼び出していきます。
条件分岐の記載順序とは前後しますが、
ポイントであるマージ処理は else 句のところです。
引数の配列を単純に２分して mergesort (＝自分自身) を呼び、
その結果を leftArr と rightArr でそれぞれ受け取ります。
これらはソート済み状態の配列になっているので、
それぞれの先頭を見比べて小さい方を取り出す、を繰り返せば
マージしたソート済み状態の配列ができあがり、
それを結果として返却していきます。
また、条件分岐の冒頭部分に戻って見ていくと、
配列の分割を繰り返すことで要素が１つか２つになるので、
１つならそのまま、２つならそれらを比較した結果を返します。
最小単位でのソートはこれで完了となるため、
あとは呼び出し元側の mergesort で併合してくれるので、
最終的に最初の呼び出しまで戻ったら、全体のソートが完了します。
最後に可視化する部分ですが、
ここで実装したマージソートはインプレースではなく、
画面表示してない別の配列（先ほどのleftArr と rightArr）を
用いてソートしているので、実は中身を表現しきれていません。
よってインデックスの動きだけを雰囲気で表現しています。
緑は分割した左側、青は分割した右側のインデックスで、
緑と青のそれぞれ小さいほう（見えない）を取っていっており、
赤がマージした分だけ進んでいく、という見え方になっています。
やる気が出たらいい感じに見せる方法を検討したいです。
最後に
記事を分けていったら５本にもなってしまいました。
JavaScriptとかアルゴリズムを勉強しはじめた、ぐらいの方への
何らかヒントになれば幸いです。
また、他にもソートアルゴリズムはいろいろあるので、
そのうち追加してみようと思います。
（解説はしませんでしたが、シャッフルするクラスが既にあるので、
ボゴソートなら１０秒くらいで実装できそうでしたが、
延々とデータを散らかし続けても仕方がないのでやめました。
疲れているときは見てると癒されるかもしれません。）