LoginSignup
0
0
@w0rc

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

Posted at

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

HTML の <canvas> 要素と JavaScript で、
ソートアルゴリズムを可視化してみました。

ソースコードはこちらに置いてあります。
README 記載の github pages にて動作がご覧いただけます。

ソースファイルの構成

フォルダ構成はこんな感じです。

root
├── css
│   └── main.css
├── scripts
│   ├── algorithms.js
│   ├── main.js
│   └── util.js
└── index.html

これと言って特別なものは何もありません。
実行に必要なものは何らかのブラウザのみで、
index.html を開けば動き出します。
index.html と main.css は、必要最低限の内容を用意しています。

index.html
<!DOCTYPE html>
<html lang="ja">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <link rel="stylesheet" href="./css/main.css">
        <script type="text/javascript" src="./scripts/util.js" charset="utf-8"></script>
        <script type="text/javascript" src="./scripts/algorithms.js" charset="utf-8"></script>
        <script type="text/javascript" src="./scripts/main.js" charset="utf-8"></script>
    </head>
    <body>
        <div id="wrapper">
            <canvas id="canvas"></canvas>
        </div>
    </body>
</html>
main.css
@charset "UTF-8";
/* global */
*{
	margin: 0;
	padding: 0;
}
body{
	background-color: #333333;
}

/* wrapper */
#wrapper{
	position: fixed;
	width: 100%;
	height: 100%;
}

ここで <canvas> 要素についてのちょっとした工夫として、
css で 幅と高さを 100% で指定した <div id="wrapper"> で囲み、
JavaScript 側で表示サイズの変更に追従できるようにしてたりします。
そのあたりはプログラム部分の解説で触れたいと思います。

プログラムの解説 - メイン処理

思いついたことを適当に詰め込んでしまっており、
ごちゃごちゃしています。申し訳ございません。
それでは main.js の内容からご覧ください。

メイン処理その１

main.js より抜粋（メイン処理その１）
～～(ここまで省略)～～

/**
 *  メイン処理
 */
function main () {
    // 描画管理クラス
    const drawManager = new DrawManager( "canvas" );
    // 描画データの準備
    const NUM = 128;
    const data = Array( NUM ).fill().map( ( _, i ) => i + 1 );
    const seed = Date.now();
    const shuffledData1 = FisherYatesShuffle.shuffle( data.slice( 0, NUM / 4 ), seed );
    const shuffledData2 = FisherYatesShuffle.shuffle( data, seed );
    // 描画対象のソートアルゴリズムの準備
    const ALGORITHMS = [
        new BubbleSort( shuffledData1 ),
        new SelectionSort( shuffledData1 ),
        new InsertionSort( shuffledData1 ),
        new QuickSort( shuffledData2 ),
        new MergeSort( shuffledData2 ),
        // おまけ. シャッフルアルゴリズムの可視化. 
        new FisherYatesShuffle( data, seed )
    ].values();
    let algorithm = ALGORITHMS.next().value;
    let iterator = algorithm.generator();

～～(以下省略)～～

main 関数で、もろもろの準備を行います。

DrawManager クラスに、canvas 要素の描画を担当してもらいます。
クラスの中身については別途。
data に、1 ~ 128 までの数字を入れてシャッフルして
shuffledData を作っています。
こちらのデータを各アルゴリズムにソートしてもらいます。
（なおここでは、アルゴリズムによって対象データ数を変えています。）

ちなみにシャッフルに使っている FisherYatesShuffle クラスは、
フィッシャー・イェーツのシャッフル」を実装したもので、
O(n) でソートが完了する優れものです。

そして、ALGORITHMS に放り込んだ各アルゴリズムクラスを取り出し、
順番に描画していきます。
ここで「順番に取り出す」を実現するのにイテレータが登場します。
[配列].values() と ALGORITHMS.next().value のところですね。

ここはイテレータであることに深い意味は無いのですが、
各アルゴリズムクラスにもジェネレータを持たせてあり、
そちらでもイテレータを取り出せるようにしています。

通常は、ソート処理の際に「途中で止める」なんてことは必要ないのですが、
今回は、イテレータ・ジェネレータの仕組みを応用して
ソートの途中状態を取り出して canvas に描画するというやり方で
可視化を実現しています。

メイン処理はもう少し続きます。

メイン処理その２

main.js より抜粋（メイン処理その２）
～～(メイン処理その１ のつづき)～～

    // 時間計測の準備
    const timer = new Timer();
    // 描画ハンドリング用の設定値
    const handler = {
        id : undefined,
        start : performance.now(),
        interval : 1000 / 30,
        done : false,
    };
    /**
     * 描画用のループ. requestAnimationFrame のコールバック関数とする
     * @param {number} timestamp requestAnimationFrame のコールバック引数で渡されるタイムスタンプ
     */
    function loop ( timestamp ) {
        // 描画タイミングを調整
        if ( handler.interval > timestamp - handler.start ) {
            handler.id = window.requestAnimationFrame( loop );
            return;
        } else {
            handler.start = timestamp;
        }
        // イテレータを進める（処理時間計測のため、タイマーのポーズを解除）
        timer.resume();
        const result = iterator.next();
        // イテレータの結果をチェック
        if ( result.done ) {
            // イテレータが完了した場合
            // タイマーをストップしてアニメーションをキャンセル
            const time = Math.round( timer.stop() * 100 ) / 100;
            handler.id = window.cancelAnimationFrame( handler.id );
            // 結果を表示する
            const resultStrings = [];
            resultStrings.push( {
                str: `Algorithm: ${algorithm.constructor.name}` +
                    `, count: ${result.value.loops}` +
                    `, swap: ${result.value.swaps}` +
                    `, time: ${time} [ms]` +
                    `, sample: ${result.value.data.length}`,
                line: 1
            } );
            // 次のアルゴリズムを取り出す
            algorithm = ALGORITHMS.next().value;
            if ( algorithm ) {
                // 次のアルゴリズムがある場合はイテレータを取得
                iterator = algorithm.generator();
                resultStrings.push( { str: `Click to Next! (${algorithm.constructor.name})`, line: 2 } );
            } else {
                // 次のアルゴリズムがない場合は終了状態とする
                handler.done = true;
                resultStrings.push( { str:  "The end. Thank you for using.", line: 2 } );
            }
            // 描画して待機
            timer.reset();
            drawManager.drawData( result.value );
            drawManager.drawString( ...resultStrings );
        } else {
            // イテレータが続く場合
            // タイマーはポーズして次回の処理まで待機
            timer.pause();
            // 描画して次のループへ
            drawManager.drawData( result.value );
            drawManager.drawString( { str: `Algorithm: ${algorithm.constructor.name}`, line: 1 } );
            handler.id = window.requestAnimationFrame( loop );
        }
    }
    
～～(以下省略)～～

最初に Timer クラスをインスタンス化していますが、
ソート処理にかかった時間（概算）を表示するのに使っており、
必須の要素ではないので、いったんおいときます。

ちょっとボリュームがあるので、処理構造に分けて解説します。

ブラウザアニメーション

まず、ブラウザでアニメーションを行う際に使うのがこちらの
window.requestAnimationFrame です。

詳細は MDN のドキュメントにあるとおりですが、
ここで渡したコールバック関数が「ブラウザ側から呼び出される」ことで、
アニメーション処理を実現できるようにするものです。

なお「呼び出しタイミング」はブラウザ依存になっています。
そのため、コールバック関数が呼び出された時間（※）を使って、
描画タイミングを調整します。
※コールバック関数の引数として渡してくれます

上記をふまえ、main.js からアニメーションループの仕組みだけを
取り出してみると、以下のイメージになっています。

main.js でアニメーションを実現している構造
    // アニメーションをハンドリングするための変数
    const handler = {
        start : performance.now(), // 前回呼び出された時間
        interval : 1000 / 30,      // アニメーションの間隔(≒FPS)
    };
    
    // requestAnimationFrame に渡すコールバック関数
    function loop ( timestamp ) {
        // timestamp に今回の呼び出し時間が入っているので、
        // 前回の呼び出し時間(handler.start)を差し引くと呼び出しの間隔が分かる
        if ( handler.interval > timestamp - handler.start ) {
            // interval 未満で呼び出されたらやり直し
            window.requestAnimationFrame( loop );
            return;
        } else {
            // interval を過ぎたら、今回の呼び出し時間を覚えて処理継続
            handler.start = timestamp;
        }
        
        (次項："フレームごとのアニメーション処理"を参照)

        // 自分自身をコールバックに指定して、次のフレームへ
        window.requestAnimationFrame( loop );
    }

いわゆる再帰処理のようなものになっており、
loop 関数の中で requestAnimationFrame( loop ) を呼び出して
１フレームずつアニメーションを進めていきます。

さらに、interval 時間未満での呼び出しに対しては、
やり直しを要求することで描画処理をするタイミングを調整します。
ここでは、1000/30 [ms] 未満、およそ最大 30 [FPS] まで、
という制限を設けていることになります。

なお、上記のままだと アニメーションはスタートしません。
どこかで 最初の requestAnimationFrame の呼び出し が必要です。
このプログラムでは別の場所で行いますので、「メイン処理その３」で説明します。

ちなみにこの枠組みはいろいろと流用可能なので、
何かしらをアニメーションさせたいときに使ってみてください。

フレームごとのアニメーション処理

つづいて、main.js で行っているアニメーション処理の部分です。
※タイマー関連の処理を省いています

メイン処理その２ での アニメーション処理
        // イテレータを進める
        const result = iterator.next();
        // イテレータの結果をチェック
        if ( result.done ) {
            // イテレータが完了した場合
            handler.id = window.cancelAnimationFrame( handler.id );
            // 結果を表示する
            const resultStrings = [];
            resultStrings.push( {
                str: `Algorithm: ${algorithm.constructor.name}` +
                    `, count: ${result.value.loops}` +
                    `, swap: ${result.value.swaps}` +
                    `, sample: ${result.value.data.length}`,
                line: 1
            } );
            // 次のアルゴリズムを取り出す
            algorithm = ALGORITHMS.next().value;
            if ( algorithm ) {
                // 次のアルゴリズムがある場合はイテレータを取得
                iterator = algorithm.generator();
                resultStrings.push( { str: `Click to Next! (${algorithm.constructor.name})`, line: 2 } );
            } else {
                // 次のアルゴリズムがない場合は終了状態とする
                handler.done = true;
                resultStrings.push( { str:  "The end. Thank you for using.", line: 2 } );
            }
            // 描画して待機
            drawManager.drawData( result.value );
            drawManager.drawString( ...resultStrings );
        } else {
            // イテレータが続く場合
            // 描画して次のループへ
            drawManager.drawData( result.value );
            drawManager.drawString( { str: `Algorithm: ${algorithm.constructor.name}`, line: 1 } );
            handler.id = window.requestAnimationFrame( loop );
        }
    }

最初の result に、ソートアルゴリズムから取り出した結果が入ります。
ここでは、次の二つの状態のどちらかになります。

result オブジェクト（ソート処理が途中の場合）
{
    done : false,
    value : (ソートアルゴリズムが "yeild" で返却したデータ)
}
result オブジェクト（ソート処理が終了した場合）
{
    done : true,
    value : (ソートアルゴリズムが "return" で返却したデータ)
}

この結果 (result.done) に応じて、処理が続きます。
ロジックと解説の順番が前後してしまいますが、
「ソート処理が途中の場合」(result.done == false) は簡単です。

result.done == false のとき
        if ( result.done ) {
            ～～（省略）～～
        } else {
            // イテレータが続く場合
            // 描画して次のループへ
            drawManager.drawData( result.value );
            drawManager.drawString( { str: `Algorithm: ${algorithm.constructor.name}`, line: 1 } );
            handler.id = window.requestAnimationFrame( loop );
        }

取り出したソート処理の状態を描画管理クラスのメソッドに任せたあとで、
次の requestAnimationFrame を呼び出すだけです。

いっぽう、「ソート処理が終了した場合」(result.done == true) では
いろいろとやることがあります。

result.done == true のとき
        if ( result.done ) {
            // イテレータが完了した場合
            handler.id = window.cancelAnimationFrame( handler.id );
            // 結果を表示する
            const resultStrings = [];
            resultStrings.push( {
                str: `Algorithm: ${algorithm.constructor.name}` +
                    `, count: ${result.value.loops}` +
                    `, swap: ${result.value.swaps}` +
                    `, sample: ${result.value.data.length}`,
                line: 1
            } );
            // 次のアルゴリズムを取り出す
            algorithm = ALGORITHMS.next().value;
            if ( algorithm ) {
                // 次のアルゴリズムがある場合はイテレータを取得
                iterator = algorithm.generator();
                resultStrings.push( { str: `Click to Next! (${algorithm.constructor.name})`, line: 2 } );
            } else {
                // 次のアルゴリズムがない場合は終了状態とする
                handler.done = true;
                resultStrings.push( { str:  "The end. Thank you for using.", line: 2 } );
            }
            // 描画して待機
            drawManager.drawData( result.value );
            drawManager.drawString( ...resultStrings );
        } else {
            ～～（省略）～～
        }

window.cancelAnimationFrame は、メソッド名の通り
アニメーション（コールバック関数）の呼び出し依頼をキャンセルします。
requestAnimationFrame でコールバックの呼び出しを依頼したときに、
そのリクエストを識別する ID が返ってきます。
この ID に対して、依頼のキャンセルを行うことができます。

resultStrings は、結果表示用の文字列をまとめています。
最後に描画管理クラスに渡します。

algorithm には、「メイン処理その１」でも出てきた、
ALGORITHMS から次に描画するソートアルゴリズムを取り出します。
そして、ソート処理のイテレータを iterator に取得しますが、
ソートアルゴリズム自体もすべて処理しきった場合は、
全体的な終了状態（handler.done) とします。

最後に、処理結果の状態（このときソートが完了した状態）を、
描画管理クラスのメソッドに任せます。
なお、ここでは次の requestAnimationFrame を呼び出していません。
これについては「メイン処理その３」で説明します。

メイン処理その３

main.js より抜粋（メイン処理その３）
～～（メイン処理その２ のつづき）～～

    /**
     *  クリックイベントハンドラを設定する
     */
    window.addEventListener( "click", ( /* event */ ) => {
        // 終了状態のときは何もしない
        if ( handler.done ) return;
        // クリックごとにアニメーションを再開／一時停止する
        if ( !handler.id ) {
            handler.id = window.requestAnimationFrame( loop );
        } else {
            handler.id = window.cancelAnimationFrame( handler.id );
        }
    } );
    /**
     *  リサイズイベントハンドラを設定する
     */
    window.addEventListener( "resize", ( /* event */ ) => {
        // 画面のリサイズが発生したら、<canvas> 要素のサイズを調整する
        document.getElementById( "canvas" )
            .setAttribute( "width", document.getElementById( "wrapper" ).clientWidth );
        document.getElementById( "canvas" )
            .setAttribute( "height", document.getElementById( "wrapper" ).clientHeight );
        drawManager.redraw( );
    } );
    window.dispatchEvent( new Event( "resize" ) );

    // 準備完了後のインフォメーション
    drawManager.drawData(  );
    drawManager.drawString(
        { str: "Visualize Sorting Algorithms.", line: 1 },
        { str: `Click to Next! (${algorithm.constructor.name})`, line: 2 }
    );
    timer.reset();
    console.info ( "ready." );
}

/**
 *  DOMContentLoaded イベントハンドラを設定する
 */
if ( window.addEventListener ) {
    window.addEventListener( "DOMContentLoaded", main );
} else {
    window.alert( "対応していないブラウザです" );
    console.error( "window.addEventListener is undefined" );
}

ここで、click と resize のイベントリスナーを登録しています。

クリック時は、 handler.id を見て
requestAnimationFrame または cancelAnimationFrame を呼び出します。
これによって、画面をクリックするたびにアニメーションの開始・停止ができます。
画面ロードの時点では停止状態のままにしておいて、
クリックしたらアニメーションを開始するようになっています。

リサイズ時は、canvas 要素のサイズを、
id="wrapper" 要素(div)のサイズに合わせるよう調整しています。
これが冒頭に記載していた、ちょっとした工夫の部分ですね。
やっていること自体は単純です。
こっそり drawManager.redraw を呼び出していますが、
これについては DrawManager クラスのほうで説明します。

main 関数は、最後に準備が完了したことを画面に表示して完了です。

そして main 関数定義の外（グローバルスコープ）に戻ったところで、
DOMContentLoaded イベントリスナに、この main 関数を登録します。
これで、画面のロードが完了してから諸々の処理が実行されます。
（DOM が読み込まれていない状態だと、JavaScript から
canvas 要素が取れないといった事態が発生します。）

だいぶ長くなったので、
メイン処理(main.js)の DrawManager クラスと、
util.js および algorithms.js については別の記事にします。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0