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

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

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

https://qiita.com/w0rc/items/bb0271d6ad1afd77e133

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

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

### QuickSort クラス

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

![QuickSort.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3572938/1bed90d1-e24e-7db3-394f-9e2c3f5c2381.png)

```js: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*` が、[別のジェネレータへの委任](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/yield*) をあらわしています。

#### *partition ( arr, left, right )

クイックソートというアルゴリズムの肝にあたる部分です。
さきほどの `generator` メソッドからジェネレータを委任したのは、
このメソッドで再帰をしたかったからです。

`partition` は、引数の配列を左右に分けていきます。
具体的には、呼び出されたときに `pivot` を選定したあと、
データの先頭（左）から **`pivot` より大きい**もの、
データの末尾（右）から **`pivot` より小さい**もの、を
順番に取り出し、**それらを入れ替え**ていきます。

この動作で、**左右からの探索が交差した時点の位置**から見ると、
左側（**`pivot` より小さい**） ／ 右側（**`pivot` より大きい**）に
選り分けられた状態となります。

このようにして分割ができたところで、
**左右の配列をそれぞれ `partition` (=自分自身) に渡して**、
さらなる大小の選り分けによる分割を進めていきます。

最終的に **`pivot` との大小比較・入れ替えが発生しなくなる**、
つまり**ソート済みでない要素がなくなるまで**繰り返せば、
ソートが完了した状態を実現することができます。

赤が `partition` により `pivot` とした値で、
青が探索中の左側（`pivot` より大きい）、
緑が探索中の右側（`pivot` より小さい）をあらわし、
青と緑が入れ替わっていきます。
次に赤が動いた瞬間が、分割後の再帰呼び出しの始まりであり、
引き続き青と緑の入れ替えによってソートが進んでいきます。

### MergeSort クラス

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

![MergeSort.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3572938/ec19956f-d4db-0115-59fd-01946b25722e.png)

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

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