本記事ではクイックソートの可視化についてのプログラムを紹介しています。
JavaScriptを使っています。
クイックソートとはソートアルゴリズムの一つで、まず適当な数を選択し、ピボットと呼ばれるものをより小さい数を前方、大きい数を後方に移動させ、分割された各々のデータを、それぞれソートするというアルゴリズムのものです。
対象のデータの並びやデータの数によりますが、一般的に言って他のソート法と比べても高速なものになります。
YouTubeに動画もアップしてあるのでそちらもご覧ください↓
クイックソートの可視化についてのプログラム
DEMO
まずこちらが完成品。
まず、棒の数（エレメント数）を１０～５００の間の数に設定し、Enter ボタンを押します。
Shuffle ボタンでシャッフルすることができます。
Start ボタンを押すとソートが始ます。
下のスライドバーでソートの速さを変更することができます。
ゆっくり見たい場合はSpeedの値を１０００にします。
本記事のコードはYouTubeのThe Coding Train というチャンネルの “Coding Challenge #143: Quicksort Visualization” という動画で紹介されているものに、シャッフル・スタートボタン、棒の数とソートの速さを変更できるものを追加しただけのものです。
HTMLファイルの作成
まず、下記のようにHTMLファイルを作成します。
JavaScript ファイルの作成
JavaScript ファイルは以下のように書きました。
まず、１行目でHTMLファイルで用意したキャンバスとの関連付けをし、２行目で描画の機能をオンにしています。
４～１０行目ではボタンやスライダーの要素を取得するために document.ElementById() メソッドを使っています。
１２～１５行目で、speed の値をスライダーバーから読み取ったものにし、また oninput というものを使用し、値が変更されたら新しい数字に更新しそれを画面に表示しています。（output.innerHTML）
getRandomDouble(min,max) 関数では与えられた数、 min ~ max までの間の数をランダムに生成しています。
shuffle() 関数で棒の高さを０～キャンバスの高さまででランダムな値にしています。
そして、draw() 関数で棒の描画を行っています。
その際、 clearRect() メソッドを使い、画面をリセットし更新時に前の描画の情報が残らないようにしています。
また、長方形を描画する際は、まず beginPath() でパスの初期化をし、ctx.rect() で長方形を描き、fill() メソッドでその棒を塗りつぶしています。
stroke() と書くことで外枠を描画しています。
指定された時間だけ処理を止めることができる手段として sleep() 関数を使っています。
swap(arr, a, b)関数は与えられた配列 arr の a と b の要素を入れ替えるためのものです。
そして、quicksort() と patition() を使い配列のソートを行っています。
その際 async と await を用い、可視化できるようにしています。
async function内でPromiseの結果が返されるまで待機するように await 演算子を使っています。
クイックソートのアルゴリズムについてはこちらの記事に詳しく書かれています。
（「ソースコード探検隊 」/ クイックソート）
gameLoop() 内に書かれた処理を一定の間隔でループをさせています。
states 配列の値によって棒の色を変更しています。
そして、addEventListener() というものを使用しボタンが押されたときにする動作を設定しています。
以上、クイックソートの可視化についてのプログラムでした。
- GitHubのコード
参考資料
- The Coding Train : “Coding Challenge #143: Quicksort Visualization“
- ソースコード探検隊 : クイックソート
コメント