ソートアルゴリズムを可視化してみよう（５）

JavaScript によるソートアルゴリズムの可視化

こちらのつづきです。
これで最終回です。

プログラムの解説 - ソートアルゴリズム（２／２）

algorithms.js で、クイックソートとマージソートの実装です。
これらは平均計算量が $O(n\ log\ n)$ のシリーズです。
このへんは処理の様子がちょっと分かりづらいので、
main.js 側から呼び出すときにデータを多めに渡すことで
俯瞰できるようにしてあります。

QuickSort クラス

クイックソートを実装します。
データから適当な値を取り出して（※）、
それより小さいもの／大きいものに選り分ける、を繰り返して
ソートを完了させていきます。
※この値の取り方は計算量に関わる重要ポイントですが、
　今回は、渡された区間の真ん中を取るだけにしています。

algorithms.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 クラス

マージソートを実装します。
データの分割と、分割した配列の併合 (マージ) を繰り返して、
ソートを実現するものです。
このマージの際に、小さい（あるいは大きい）ほうを取り出す、
というルールを設けることで、結果的にソートされる仕組みです。

algorithm.js 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とかアルゴリズムを勉強しはじめた、ぐらいの方への
何らかヒントになれば幸いです。

また、他にもソートアルゴリズムはいろいろあるので、
そのうち追加してみようと思います。
（解説はしませんでしたが、シャッフルするクラスが既にあるので、
ボゴソートなら１０秒くらいで実装できそうでしたが、
延々とデータを散らかし続けても仕方がないのでやめました。
疲れているときは見てると癒されるかもしれません。）