JavaScript によるソートアルゴリズムの可視化
こちらのつづきです。
プログラムの解説 - ソートアルゴリズム（１／２）
ようやく algorithms.js の部分に入ります。
ソートの仕組み自体は、世の中にいくらでも詳しい解説があるので、
このプログラムでの実装ポイントについて書きたいと思います。
今回は、平均計算量が $O(n^2)$ のシリーズを取り上げます。
このプログラムの中では以下のアルゴリズムを実装しています。
- バブルソート
- 選択ソート
- 挿入ソート
VisualizedAlgorithm クラス
さっそく横道に逸れますが、
main.js からソートを順番に呼び出していくために、
各ソートアルゴリズムには共通のインターフェースを
持っていて欲しいです。
というわけで、各ソートアルゴリズムの実装に入る前に、
各クラスの基底となるクラスを作っておきます。
/**
* 描画用アルゴリズムのベースクラス
*/
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 クラス
ここからソートアルゴリズムクラスの説明です。
バブルソートを実装します。
大きいデータがのぼっていくのが泡のよう、だそうです。
/**
* バブルソート 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 クラス
選択ソートを実装します。
小さいものを探して前に持ってくるソートです。
/**
* 選択ソート 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 程度しかない場合では、
クイックソートやマージソートよりも処理が速かったりします。
/**
* 挿入ソート 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
挿入ソートの中身です。
取り出したデータを、ソート済み範囲の中で
それより小さいものがない位置まで交換します。
青が入れ替え作業中の取り出したデータで、
緑はソート済み部分の中で青よりも大きいデータなので
それらが入れ替わっていきます。
赤はソート済み範囲の末尾を示すものになっています。
今回はここまでとなります。
次回が最終回で、クイックソートとマージソートの実装です。