とあるIT企業のインフラエンジニア。プライベートでは開発もちょっとやります。
※本ブログの内容はすべて個人の見解であり、所属する企業とは関連ありません。
2023/09/30 暫く更新停止中m
生活・子育て(10)
FaaS(1)
働き方(2)
SaaS(2)
自作PC(6)
IT入門(1)
IaaS(13)
IDaaS(2)
ITIL(1)
PHP(2)
OS(6)
システム監視(1)
コミュニティ(1)
PCアプリ(10)
ストレージ(4)
ブログ(9)
ActiveDirectory(2)
デバイス(7)
旅行(10)
デザイン(3)
カンファレンス(5)
セキュリティ(9)
インフラ(19)
コーディング(11)
ゲーム(28)
インターネット(18)
未分類(8)
88 [今日]
660 [昨日]
【アルゴリズム】ヒープソートの動きを見たい
2021/06/01
コーディング
お疲れ様です。
しらせです。
久しぶりにYoutubeでソート(並び替え)アルゴリズムの動画を見ました。
選択ソート、クイックソート、シェーカーソート、挿入ソート、シェルソートなど見慣れたソートアルゴリズムから、基数ソート、バイトニックソート、ボゴソートなど面白いソートまで幅広く見れて何度見ても飽きないです。
そこで今日は気になっているソートアルゴリズムを1つブラウザで表現できるように実装してみようと思います。
もくじ
はじめに
ソートアルゴリズムの中でも一番好きなのはもちろん「ヒープソート」ですよね?
配列を操作するだけで紹介動画にもあるように片側からじわーっと順番に並んでいく様子は本当に素晴らしいですね!
ヒープの仕組み自体はメモリ管理などでよく聞きます。聞くだけです。
ヒープソートの計算量(オーダ)はNlogNでめちゃくちゃ優れているというわけではありませんし、安定ソートでもないので何がメリットなの?という感じではありますが。
詳細は以下をご参照ください。
ヒープソート - ウィキペディア(Wikipedia
ブラウザで実行したい
紹介動画みたいにきれいに並んでいく様子を自分でも作ってみたい!!!
そう思ってさっそくサンプルコードを調べながらJavascriptとDOM操作で実装しようとしました。
<参考にさせて頂いサイト>
http://www.th.cs.meiji.ac.jp/assets/researches/2005/omoto/heapsort.html
実際に手元のPCで実装できたものの、肝心の「じわーっ」と並んでいく様子がみれない。。。
「実行」 → 「並び替え」 の2つの状態しか見れないじゃないか!
処理が速すぎるのか?
「sleepを挟めばいいんじゃね?」(アホ)
※Javascriptはsleepなんて無いし処理が終わるまで描画されないことを知らないまま取り掛かったのが終わりの始まりでした。
sleep無いじゃん。
SetTimeout? うーんだめだな。
SetInterval? だめだ。
requestAnimationFrame? どう使うんだ??
リフローやリペイントを発生させればいい?
いっそ他の言語でやろうか、、できればミリ秒で。。いや表示が無理か。。
whileとdateのループで行けるか? 無理だな。
。。。
。。。
。。。
まとめ
できました!!!!
ヒープソート
https://fsbblog.jp/software/heapsort/heapsort.html
Windows10のChromeと、Android10のChromeと、iPhone11Pro(iOS13)のSafariで動作確認できました。
ただし、IEはダメです。(FND)
※動作の際はPCやスマホに負荷がかかる場合がありますのでご注意ください。
※自己責任でご利用くださいませ。
結局、すべての並び替えを一度書き出して順にグラフに当てはめるというなんともしょぼいやり方になりました。
最初の処理で時間がかかるのもゴミ。
まぁ動いたのでokです。
ヒープソートは神
以上
お疲れさまでした。