はじめに
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で動かすことにより、サーバサイドで動かすことができるようになります。
