概要
普段からよくソートを使っているので動きを理解するためにHTML+Canvasを用いて可視化をしてみました
クイックソートの実装
クイックソートの概要
クイックソートとは、とある基準値よりも大きい値の配列と小さい値の配列に分割してそれを再帰的に適用することで並び替えを行うアルゴリズムです。高速なソートアルゴリズムとして知られています
- 適当な基準値を決めます(※1)
- 配列を基準値より小さい値の配列と大きい値の配列に分割します(※2)
- 分割できなくなるまで1～2を繰り返します
- 分割できなくなったら配列を結合します
- ※1 中央値を基準値として扱えると効率の面で最適ですが、今回の記事は配列の先頭の値を基準値として扱います
- ※2 今回は視覚化を目的とするため配列は分割せずに実装します
実装
TypeScriptでソート関数を以下のように実装しました。
- array T[] ソート対象の配列
- compareFunction: (a: T, b: T) => boolean 比較用の関数
- option
- start?: number ソート対象の範囲の先頭のインデックス
- end?: number ソート対象の範囲の最後尾のインデックス
- fn? 比較が行われるたびに呼ばれる関数。今回は視覚化のために使います
/**
*
* @param array ソート対象の配列
* @param compareFunction 比較関数(昇順: a < b)
* @param option ソートの範囲やステップごとに呼ばれる関数など
* @returns
*/
async function qsort<T>(array: T[], compareFunction: (a: T, b: T) => boolean, option?: { start?: number, end?: number, fn?: (array: T[], i: number, pivot: number) => Promise<void> }): Promise<T[]> {
//ソート対象の範囲
const start = (option?.start != undefined) ? option.start : 0;
const end = (option?.end != undefined) ? option.end : array.length;
//基準値
let pivot = start;
//要素数が2以下であれば返す
if (end - start < 2) return array;
for (let i = Math.max(start, 0) + 1; i < Math.min(end, array.length); i++) {
//比較した結果に応じて配列を並び変える(本来なら2つの配列に分ける)
if (compareFunction(array[i], array[pivot])) {
array.splice(pivot, 0, array[i]);
array.splice(i + 1, 1);
pivot++;
}
//オプションで関数が与えられていた場合呼び出す
if (option?.fn) await option.fn(array, i, pivot);
}
//再帰的にソート関数を呼び出す
array = await qsort(array, compareFunction, { start: start, end: pivot, fn: option?.fn })
array = await qsort(array, compareFunction, { start: pivot + 1, end: end, fn: option?.fn });
return array;
}
グラフの実装
Canvasを用いて簡易的なグラフを実装しました
Graphクラスは以下のメンバ変数とメンバメソッドを持ちます
- 変数
- private canvas: HTMLCanvasElement; 描画する対象
- private parent: HTMLElement; 描画対象の親要素
- private data: { value: number, color: string }[]; 数値と棒の色の配列
- private size: { width: number, height: number }; 描画対象のサイズ
- private max: number; グラフの最大値
- メソッド
- constructor(graphID: string, max: number) コンストラクタ。描画対象とグラフの最大値を引数にとる
- private resize() 描画対象を親要素のサイズにリサイズする。後述するdraw()から呼ばれる
- draw() グラフを描画する
- setData(data: { value: number, color: string, }[], max?: number) データをセットする。グラフの値の配列と最大値を引数にとる
これらを以下のように実装しました
class Graph {
private canvas: HTMLCanvasElement;
private parent: HTMLElement;
private data: {
value: number,
color: string,
}[];
private size: { width: number, height: number };
private max: number;
/**
*
* @param graphID
* @param max グラフの最大値
*/
constructor(graphID: string, max: number) {
let graph = document.getElementById(graphID);
if (graph && graph.tagName == 'CANVAS') {
this.canvas = graph as HTMLCanvasElement;
}
else {
throw new Error("graph is not canvas");
}
const parent = this.canvas.parentElement;
if (!parent) {
throw new Error("parent is null");
}
this.parent = parent;
this.size = { width: 0, height: 0 };
this.data = new Array();
this.max = max;
}
private resize() {
this.size.width = this.parent.clientWidth;
this.size.height = this.parent.clientHeight;
this.canvas.setAttribute('width', this.size.width.toString());
this.canvas.setAttribute('height', this.size.height.toString());
this.canvas.width = this.size.width;
this.canvas.height = this.size.height;
}
draw() {
this.resize();
const context = this.canvas.getContext('2d');
if (!context) {
return;
}
//背景を黒で塗りつぶす
context.beginPath();
context.rect(0, 0, this.size.width, this.size.height);
context.fillStyle = "black";
context.fill();
context.closePath();
//サイズの計算
const width = this.size.width / this.data.length;
const heightScale = this.max / this.size.height;
//棒グラフの描画
for (let i = 0; i < this.data.length; i++) {
context.beginPath();
context.rect(i * width, this.size.height - (this.data[i].value / heightScale), width, this.size.height);
context.fillStyle = this.data[i].color;
context.fill();
context.closePath();
}
}
/**
*
* @param data グラフの値と色の配列
* @param max 最大値
*/
setData(data: { value: number, color: string, }[], max?: number) {
this.data = data;
if (max) this.max = max;
}
}
実際に動かしてみる
実装
-
async function draw(a: number[], _i: number, pivot: number)- こちらの関数はソート関数に渡すことで配列の並び替えのたびに呼ばれる関数です
- 棒グラフの色の設定を行います
- 一定時間待った後にグラフにデータを登録して描画します
-
array = await qsort(a, () => { return Math.random() - 0.5 < 0 }, { fn: draw });- 配列のシャッフルのためにクイックソートを流用しています
-
array = await qsort(array, (a, b) => { return a < b }, { fn: draw });- 昇順でソートします
実際に動作させるためのコードを以下のように記述します
const wait = async (ms: number) => new Promise(resolve => setTimeout(resolve, ms));
async function main() {
//配列の初期化
let array: number[] = new Array();
for (let i = 0; i < 256; i++) {
array.push(i);
}
const g = new Graph('graph', array.length);
async function draw(a: number[], _i: number, pivot: number) {
const data: { value: number, color: string, }[] = new Array();
for (let i = 0; i < a.length; i++) {
if (i == _i) {
data.push({ value: a[i], color: "green" });
}
else if (i == pivot) {
data.push({ value: a[i], color: "red" });
}
else {
data.push({ value: a[i], color: "lightblue" });
}
}
await wait((1 / a.length) * 10000);
g.setData(data);
g.draw();
return;
}
while (true) {
//シャッフル
array = await qsort(array, () => { return Math.random() - 0.5 < 0 }, { fn: draw });
//ソート
array = await qsort(array, (a, b) => { return a < b }, { fn: draw });
}
}
main();
HTMLは以下のように記述します
<div style="width: 50vw; height: 25vw;">
<canvas id = 'graph'></canvas>
</div>
<script src="./main.js"></script>
コンパイルして実行確認
TypeScriptはブラウザ上では動作しないのでtscコマンドでコンパイルします(パスは環境に合わせてください)
$ tsc ./src/main.ts
htmlファイルをブラウザで開くと以下の画像のようにグラフが表示され並び変えられる様子が見られます
赤色のグラフが基準となる値を示しており、緑色が基準値と比較したい値を示しています。左から右へと順に基準値と比較をしていき、基準値より小さいものを赤色の左側へ、大きいものを赤色の右側へと移動します
これを繰り返すことで配列が並び変えられる様子が視覚的に理解することができます
See the Pen Untitled by mm (@NXTEDmm) on CodePen.
まとめ
今回はCanvasを用いてクイックソートの可視化をしてみました
基準値より大きい値と小さい値で別けられていることが視覚的にわかりやすく見ていて面白いものが作れたと思います
この記事が参考になれば幸いです。最後までご覧いただきありがとうございました