kabablog
Programming

【やり直しJavascript】ソートアルゴリズムを可視化してみる(バブルソート)その1

はじめに

Javascriptを久しぶりに触っています。仕事で使っているわけではないのですが、せっかく勉強したのにもったいないので、思い出すつもりで書いています。

ただ、実戦でもまれたわけでもないため、ベストプラクティスではないことが前提となります。(アドバイスいただけると嬉しいです)

何を作る

ソートアルゴリズムをビジュアライズするページ(Sorting Algorithms Animations)を見て、同じようなものを作ってみたいと思い作ってみました。

ソートアルゴリズムとは

Googleで調べると解説ページがたくさんあります。僕はこちらを参考とさせていただきました。

また、調べてみると、こちらのページはUnityを使ってソートアルゴリズムを可視化していました。僕もここまでやりたいですが、まだまだ時間かかりそうです。

バブルソート

今回はバブルソートを使ってみたいと思います。理由はアルゴリズムがシンプルだからです。

以前は、クイックソートを作ったのですが、アルゴリズム自体は再帰関数を使えばできそうなのですが、可視化の実装がちょっと大変過ぎた記憶しかないため、今回はシンプルなものにしました。(setTimeout()関数と再帰関数との組み合わせあたりが・・・)

しかし、時間があれば挑戦してみます。

イメージ

イメージは以下です。Sortボタンを押すとちょっとずつバーが動いて整列するようなアニメーションです。

配置をする

アルゴリズムを実装する前に、HTMLを組み立てたいと思います。

<html>
  <head>
    /* あとで書く */
  </head>
  <style>
    /* 省略 */
  </style>
  <body>
    <div id="title"></div>
    <button id="array-submit">Sort</button>
    <script type="text/javascript">
        let array = new Array();
        const array20 = [12, 9, 15, 19, 6, 11, 20, 2, 18, 14, 10, 4, 17, 8, 5, 13, 3, 16, 7, 1];

        array = array20;

        document.getElementById("array-submit").addEventListener("click", {name: array, handleEvent: sortItems});

        function sortItems(event) {
            // Sortボタンを押した後の処理を書く
        }

//・・・・(後で書く)

  </body>

HTMLの構成、<head></head>と<body></body>を配置します。また、bodyタグの中で、Javascriptを実行するため、scriptタグ<script></script>を用意し、中で処理を定義します。

まず、Javascriptの実行の起点となるボタンを配置し、処理を定義します。

<button id=”array-submit”>Sort</button>という形でボタンを定義します。このあと、document.getElementById(“array-submit”).addEventListener(“click”, {name: array, handleEvent: sortItems});という形でクリックした際の処理を付けます。また、入力として配列があります。適当に並べた1~20の数値を配列に入れていきます。

ボタンを押した後、sortItems()関数を呼ぶため、sortItem()関数を定義します。

アルゴリズムを実装する

バブルソートは隣り合う値を比べて、値が大きい方を右側(上のイメージの場合)に置く形になります。

    let sorted = false;
    let counter = 0;
    
    while (sorted === false) {
        let swapsMade = false;
        for (let i = 0; i < array.length; i++) {
            counter++;

            if (array[i + 1] < array[i]) {
                [array[i], array[i + 1]] = [array[i + 1], array[i]];
                swapsMade = true;
            }
        }
        if (swapsMade === false) {
            sorted = true;
        }
    }

「Sort」ボタンと連携したいので、関数化しつつ、アニメーションを制御する関数も入れてみます。

    <script type="text/javascript">
        let array = new Array();
        const array20 = [12, 9, 15, 19, 6, 11, 20, 2, 18, 14, 10, 4, 17, 8, 5, 13, 3, 16, 7, 1];

        array = array20;

        document.getElementById("array-submit").addEventListener("click", {name: array, handleEvent: sortItems});

        function sortItems(event) {
            let sorted = false;
            let counter = 0;
            
            while (sorted === false) {
                let swapsMade = false;
                for (let i = 0; i < array.length; i++) {
                    // グラフ描画用の関数を呼び出す(別途関数を定義する)
                    counter++;

                    if (array[i + 1] < array[i]) {
                        [array[i], array[i + 1]] = [array[i + 1], array[i]];
                        swapsMade = true;
                    }
                }
                if (swapsMade === false) {
                    sorted = true;
                }
            }
            return array;
        }

可視化する

D3.JS

グラフ描画はD3.JSというライブラリを使いました。そのため、headタグ内に<script src=”https://d3js.org/d3.v5.min.js”></script>という形でD3.JSのライブラリを取り込む必要があります。

各関数の説明です。

setAnimation()は描画処理の制御をします。setTimeout関数を使って、描画タイミングを調整します。また、CSSなどを使わないで描画処理を呼んでいるため、再描画するためには既存の描画領域を削除する処理が必要でした。d3.select(“svg”).remove()で削除します。


makeObj()はD3.JSのグラフ描画に必要な入力値のデータセットを整形します。配列型で渡されるので、D3.JSのインプットのオブジェクト型に変換します。


makeGraph()はmakeObjで作成したデータセットおよび、グラフのパラメータをセットし、D3.JSの呼び出しを行います。

 function setAnimation(counter, array, i){
     setTimeout(() => {

         // 再描画用に要素を削除
         d3.select("svg").remove();

         // グラフを描画する
         makeGraph(makeObj(array));
     }, counter * 100);
 }

 function makeObj(array){
     // D3.jsインプット用オブジェクトと配列を初期化
     let obj = new Object();
     let resArr = new Array();

     // データを変換し、オブジェクト配列を作る
     for(let i = 0; i < array.length; i++){
         obj = new Object();
         obj["name"] = array[i];
         obj["value"] = array[i];
         resArr.push(obj);
     }
     return resArr;
 }

 function makeGraph(dataset) {
 // 後ほど説明します。
}

makeGraph()は以下のサイトを参考にしました。今回は「データの準備」の部分だけを外部からのインプットとするmakeGraph関数として定義しており、内部の処理は以下のサイトを参考とさせていただいています。解説がとても分かりやすいです。

データビジュアライゼーション・ラボさんのページ

また、このままだと、初期表示されないので、初期表示用に一回呼び出しを行います。配列の定義と、ボタン押下時の処理前に入れておきます。

        let array = new Array();
        const array20 = [12, 9, 15, 19, 6, 11, 20, 2, 18, 14, 10, 4, 17, 8, 5, 13, 3, 16, 7, 1];

        array = array20;

        makeGraph(array); // ここに追加
        document.getElementById("array-submit").addEventListener("click", {name: array, handleEvent: sortItems});

後は、書きあがったHTMLファイル(名前はなんでもよく、拡張子を.htmlにします)をブラウザで表示し、実行します。

終わりに

今回はHTMLにJavascriptを埋め込む形で実装してみました。次は、Node.JS上で動かしてみたいと思います。

Node.JSで動かすことにより、サーバサイドで動かすことができるようになります。

Blog Ranking Site

よかったら応援クリックお願いします!

にほんブログ村 旅行ブログ 東南アジア旅行へ
にほんブログ村 にほんブログ村 旅行ブログへ
にほんブログ村 PVアクセスランキング にほんブログ村