ByProduct - 副産物

IT FukuSanButsu Blog

社内インフラエンジニアの自宅からはじまるIT
自宅のPCに向き合いながら気づいたことや個人的な知見をまとめています


プロフィール
しらせ(HN)
とあるIT企業のインフラエンジニア。プライベートでは開発もちょっとやります。
※本ブログの内容はすべて個人の見解であり、所属する企業とは関連ありません。
2023/09/30 暫く更新停止中m
プロフィールを読む
カテゴリ別
内部リンク
相互リンク

Twitter
来訪
1178301 [合計]
88 [今日]
660 [昨日]
Powered by
Powered by AWS Cloud Computing


【アルゴリズム】ヒープソートの動きを見たい

2020/04/25
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です。
ヒープソートは神

以上
お疲れさまでした。



View:2094 この記事をツイート!