【JavaScript】プログラミングでクイックソートの可視化

JavaScript
スポンサーリンク

本記事ではクイックソートの可視化についてのプログラムを紹介しています。

 

JavaScriptを使っています。

 

クイックソートとはソートアルゴリズムの一つで、まず適当な数を選択し、ピボットと呼ばれるものをより小さい数を前方、大きい数を後方に移動させ、分割された各々のデータを、それぞれソートするというアルゴリズムのものです。

 

対象のデータの並びやデータの数によりますが、一般的に言って他のソート法と比べても高速なものになります。

 

YouTubeに動画もアップしてあるのでそちらもご覧ください↓

 

【6倍速】クイックソートの可視化 / JavaScript 【プログラミング】
スポンサーリンク

クイックソートの可視化についてのプログラム

DEMO

まずこちらが完成品。

 

まず、棒の数(エレメント数)を10~500の間の数に設定し、Enter ボタンを押します。

 

Shuffle ボタンでシャッフルすることができます。

Start ボタンを押すとソートが始ます。

 

下のスライドバーでソートの速さを変更することができます。

ゆっくり見たい場合はSpeedの値を1000にします。

 

本記事のコードはYouTubeのThe Coding Train というチャンネルの “Coding Challenge #143: Quicksort Visualization” という動画で紹介されているものに、シャッフル・スタートボタン、棒の数とソートの速さを変更できるものを追加しただけのものです。

 

Coding Challenge #143: Quicksort Visualization

HTMLファイルの作成

 

まず、下記のようにHTMLファイルを作成します。

 

 

JavaScript ファイルの作成

 

JavaScript ファイルは以下のように書きました。

 

 

まず、1行目でHTMLファイルで用意したキャンバスとの関連付けをし、2行目で描画の機能をオンにしています。

4~10行目ではボタンやスライダーの要素を取得するために document.ElementById() メソッドを使っています。

12~15行目で、speed の値をスライダーバーから読み取ったものにし、また oninput というものを使用し、値が変更されたら新しい数字に更新しそれを画面に表示しています。(output.innerHTML)

 

getRandomDouble(min,max) 関数では与えられた数、 min ~ max までの間の数をランダムに生成しています。

 

shuffle() 関数で棒の高さを0~キャンバスの高さまででランダムな値にしています。

 

そして、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() というものを使用しボタンが押されたときにする動作を設定しています。

 

以上、クイックソートの可視化についてのプログラムでした。

 

 

プログラミングでバブルソートの可視化【JavaScript】
JavaScript でバブルソートの可視化についてのプログラムを実装。ソートアルゴリズムの一つバブルソートをアニメーションで再現。プログラミング入門。

 

【猿でもできるソート】プログラミングでボゴソートを可視化
ソートアルゴリズムの一つ、ボゴソートをプログラミングで可視化したものを実装しました。JavaScriptで猿でもできるソートやランダムソートとも呼ばれるボゴソートを視覚化するプログラム。

参考資料

 

 

 

ご質問・ご感想は

ツイッターお問い合わせからいただけるとうれしいです。

 

最後まで読んでくれてありがとうございます。

ツイッターのフォローもお願いします。

それではまた!
 
 


YouTubeチャンネルを開設しました。
主にプログラミングについて配信をしています。

 

 
 

JavaScript プログラミング
スポンサーリンク
この記事をSNSでシェアする
フォローする
スポンサーリンク

コメント