プロフィール
管理者:しらせ(HN)
とあるIT企業のインフラエンジニア。プライベートでは開発もちょっとやります。
※本ブログの内容はすべて個人の見解であり、所属する企業とは関連ありません。
カテゴリ別
内部リンク
[PR]
Twitter
来訪
257152 [合計]
116 [今日]
152 [昨日]
Powered by
Powered by AWS Cloud Computing

ByProduct - FukuSanButsu Blog

ふくさんぶつBlog

開発系インフラエンジニア

インフラを学ぶ学生や企業のIT担当者のために



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

Date:2020/04/25 02:03:06
Category:プログラミング


お疲れ様です。
しらせです。


久しぶりにYoutubeでソート(並び替え)アルゴリズムの動画を見ました。


選択ソート、クイックソート、シェーカーソート、挿入ソート、シェルソートなど見慣れたソートアルゴリズムから、基数ソート、バイトニックソート、ボゴソートなど面白いソートまで幅広く見れて何度見ても飽きないです。

そこで今日は気になっているソートアルゴリズムを1つブラウザで表現できるように実装してみようと思います。


もくじ

  1. はじめに
  2. ブラウザで実行したい
  3. まとめ


はじめに

ソートアルゴリズムの中でも一番好きなのはもちろん「ヒープソート」ですよね?
配列を操作するだけで紹介動画にもあるように片側からじわーっと順番に並んでいく様子は本当に素晴らしいですね!

ヒープの仕組み自体はメモリ管理などでよく聞きます。聞くだけです。
ヒープソートの計算量(オーダ)は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です。
ヒープソートは神


以上、お疲れさまでした。





Views:138 この記事をツイート!