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

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

こちらのつづきです。

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

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

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

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

VisualizedAlgorithm クラス

さっそく横道に逸れますが、
main.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 クラス

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

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

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

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

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 程度しかない場合では、
クイックソートやマージソートよりも処理が速かったりします。

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

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

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

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