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

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

こちらのつづきです。

https://qiita.com/w0rc/items/43cb12a54310f75960a8

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

ようやく `algorithms.js` の部分に入ります。
ソートの仕組み自体は、世の中にいくらでも詳しい解説があるので、
このプログラムでの実装ポイントについて書きたいと思います。

今回は、平均計算量が $O(n^2)$ のシリーズを取り上げます。
このプログラムの中では以下のアルゴリズムを実装しています。

- バブルソート
- 選択ソート
- 挿入ソート

### VisualizedAlgorithm クラス

さっそく横道に逸れますが、
`main.js` からソートを順番に呼び出していくために、
各ソートアルゴリズムには共通のインターフェースを
持っていて欲しいです。

というわけで、各ソートアルゴリズムの実装に入る前に、
各クラスの基底となるクラスを作っておきます。

```js:algorithms.js VisualizedAlgorithm クラス
/**
 *  描画用アルゴリズムのベースクラス
 */
class VisualizedAlgorithm {
    /**
     *  描画用アルゴリズムのコンストラクタ
     *  @param {Object} arr 
     */
    constructor ( arr ) {
        this.arr = [...arr];
        this.loops = 0;
        this.swaps = 0;
    }
    /**
     *  処理中のデータを返却する
     *  @returns {Object} 
     */
    yieldProperties ( ...args ) {
        return {
            data: this.arr,
            coloringIndices: args
        }
    }
    /**
     *  処理後のデータを返却する
     *  @returns {Object}
     */
    resultProperties () {
        return {
            data: this.arr,
            loops: this.loops,
            swaps: this.swaps
        }
    }
    /**
     *  処理用のイテレータを返却する
     */
    *generator () {
        yield this.arr;
    }
}
```

#### コンストラクタ

引数はソートしたいデータの配列です。
`this.arr = [...arr];` の部分についてですが、
インスタンス化するとき配列**のコピー**を保持するために、
スプレッド構文を利用した代入にしています。

`this.loops` と `this.swaps` は、
ソート処理で行う比較回数と交換回数（の目安）です。

#### yieldProperties ( ...args )

引数の `args` には、色付けしたいインデックス番号を渡します。
ソート途中のデータ状態をオブジェクト化して返却します。

#### resultProperties ( )

ソート終了後のデータ状態をオブジェクト化して返却します。
ソート処理中に比較(ループ)した回数と交換した回数をカウントし、
ここで取り出せるようにします。

#### *generator ( )

ソートアルゴリズムのイテレータを返却するジェネレータです。
各ソートクラスでオーバーライドします。

呼び出し元から イテレータの next( ) が呼ばれたら、
中間の yield では yieldProperties の内容を、
最後の return では resultProperties の内容を
返却する、というかたちになります。

### BubbleSort クラス

ここからソートアルゴリズムクラスの説明です。

バブルソートを実装します。
大きいデータがのぼっていくのが泡のよう、だそうです。

![BubbleSort.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3572938/4d71192c-4fed-79a9-f490-9ffb8506d99b.png)

```js:algorithms.js BubbleSort クラス
/**
 *  バブルソート O(n^2)
 */
class BubbleSort extends VisualizedAlgorithm {
    *generator ( ) {
        let left = 0, right = 0;
        const len = this.arr.length;
        for ( let i = 0; i < len; i++ ) {
            for ( let j = 0; j < len - i - 1; j++ ) {
                if ( this.arr[j] > this.arr[j + 1] ) {
                    [left, right] = [j, j + 1];
                    [this.arr[j], [this.arr[j + 1]]] = [this.arr[j + 1], [this.arr[j]]];
                    this.swaps++;
                }
                yield this.yieldProperties( j, left, right );
                this.loops++;
            }
        }
        return this.resultProperties();
    }
}

```

#### *generator ( ) // BubbleSort

バブルソートの中身です。
先頭から順に、大きいデータを見つけたら後ろへ入れ替えます。

青と緑のインデックスが入れ替わる様子から
ソートされていく状況が見えますね。
ちなみに赤は探索中ののインデックスなので、
ソートされていない間は青と同じなので重なって見えませんが、
ソート済み範囲を探索しているときは動きが見えます。

### SelectionSort クラス

選択ソートを実装します。
小さいものを探して前に持ってくるソートです。

![SelectionSort.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3572938/9dd296cc-2f26-a13f-77d9-633570eb3330.png)

```js:algorithms.js SelectionSort クラス
/**
 *  選択ソート O(n^2)
 */
class SelectionSort extends VisualizedAlgorithm {
    *generator ( ) {
        const len = this.arr.length;
        for ( let i = 0; i < len; i++ ) {
            let min = i;
            for ( let j = i; j < len; j++ ) {
                if ( this.arr[j] < this.arr[min] ) {
                    min = j;
                }
                yield this.yieldProperties( j, min, i );
                this.loops++;
            }
            [this.arr[i], this.arr[min]] = [this.arr[min], this.arr[i]];
            this.swaps++;
        }
        return this.resultProperties();
    }
}
```

#### *generator ( ) // SelectionSort

選択ソートの中身です。
ソート済み範囲の末尾から探索をはじめて、
探索範囲の中から最も小さいものと入れ替えていって
ソート済みの範囲を広げていきます。

青がソート済み範囲の末尾で、
赤いインデックスが探索範囲の中で動いていきます。
緑は探索範囲の中での最小データをあらわし、
新しい最小データが見つかるとその位置が変わっていって、
最後に青と緑が入れ替わります。

### InsertionSort クラス

挿入ソートを実装します。
取り出したデータを、ソート済み部分の適切な位置に挿します。

また、この挿入ソートは、
ソートするデータ量が少ない、あるいは
ソート済み範囲を知っていて新しいデータを追加したい、
というような状況において、高い性能を発揮します。

たとえば今回のように、データ数が 32 程度しかない場合では、
クイックソートやマージソートよりも処理が速かったりします。

![InsertionSort.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3572938/3548c6d6-331a-ffd5-6156-c7ac3b5bca09.png)

```js:algorithms.js InsertionSort クラス
/**
 *  挿入ソート O(n^2)
 */
class InsertionSort extends VisualizedAlgorithm {
    *generator () {
        const len = this.arr.length;
        for ( let i = 1; i < len; i++ ) {
            let j = i;
            while ( j > 0 && this.arr[j - 1] > this.arr[j] ) {
                yield this.yieldProperties( j - 1, i, j );
                [this.arr[j - 1], this.arr[j]] = [this.arr[j], this.arr[j - 1]];
                j--;
                this.swaps++;
                this.loops++;
            }
        }
        return this.resultProperties();
    }
}
```

#### *generator ( ) // InsertionSort

挿入ソートの中身です。
取り出したデータを、ソート済み範囲の中で
それより小さいものがない位置まで交換します。

青が入れ替え作業中の取り出したデータで、
緑はソート済み部分の中で青よりも大きいデータなので
それらが入れ替わっていきます。
赤はソート済み範囲の末尾を示すものになっています。

#
今回はここまでとなります。
次回が最終回で、クイックソートとマージソートの実装です。