管理者:しらせ(HN)
とあるIT企業のインフラエンジニア
Windows/Linux両方使います。
趣味でソフトウェアやWebアプリを作ってます。
すべて本業とは関係のない副産物です。
※本ブログの内容はすべて個人の見解であり、所属する企業とは関連ありません。
[PR]
カテゴリ別
デバイス(2)
旅行(1)
デザイン(3)
カンファレンス(4)
オフ会(1)
インフラ(9)
プログラミング(6)
ゲーム(17)
インターネット(12)
未分類(1)
内部リンク
Blogトップ
プライバシーポリシー
Twitter
来訪
248473 [合計]
200 [今日]
257 [昨日]
Powered by
Powered by AWS Cloud Computing
支援募集

ふくさんぶつ Blog
インフラエンジニアしらせのIT遊びブログ。
学生や中小企業の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:78 この記事をツイート!




【連載】社内インフラエンジニアのために
2020/05/04 05:42:51
【インフラ】Windows Admin CenterでWindowsServerを管理できるか
2020/03/01 23:40:09