読者です 読者をやめる 読者になる 読者になる

APPSセレクト by Android

スマホアプリ(Android)に関する情報サイト

とっつきにくいアルゴリズムを一目で理解「アルゴリズム図鑑」

レビュー

f:id:ok-alexa:20170311013514p:plain

普段なにげなく利用する検索機能。カーナビってどんな仕組みで目的地までの道順を表示させてるの?圧縮ファイルってどうやってサイズを小さくしてるの?暗号化の仕組みは? こんな普段何気なく利用しているモノの中にはたくさんのアルゴリズムが使われています。

たとえばアルゴリズムの一つ「ヒープソート」を言葉で説明すると訳が分かりません。

全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。なおこの繰り返しは、入れ替えが起こらなくなった時点で(それ以降は何度繰り返しても変化が起こらなくなるので)中断することができる。
この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。
例えば前記の特徴によりバブルソートは並列処理と親和性が高く、比較交換器を潤沢に用いることで比較交換順序を調整したハードウェア実装では時間計算量はO(n)になる。この並列処理向けに比較交換順序を調整したアルゴリズムとして奇偶転置ソートがある。
また特にソフトウェアで実装される場合には一般に先頭から順に順次処理されるものなので、逆に先頭から順に順次処理されることを利用して不要なことが自明な比較交換をしないように効率化することは有効かつ直感的であり、この効率化されたアルゴリズムをもってバブルソートと呼ぶ場合もある。さらに、比較交換順序を逆順にすることで自明な比較交換を検出し易くしたアルゴリズムに挿入ソートがあり、効率化されたバブルソートは簡単な変更で容易に挿入ソートにできることから、ソートのソフトウェア実装としてバブルソートを選択する根拠はなく、学習専用の非効率的なアルゴリズムと考えられているのが現状である。
なお、係る派生したアルゴリズムが隣接する要素と比較交換以外の比較や交換を行なうことで効率化を図っている場合、安定という特徴を失う。
以下では、前記の自明な比較交換をしないように効率化されたバブルソートに関して解説する。
要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

Wikipediaより

 

それを簡単に図解でワンステップずつ解説・説明してくれるのがこのアプリの素晴らしいところです。

f:id:ok-alexa:20170311013513p:plain

画面もシンプルで直感的に仕組みが理解できます。

プログラムを始めたいのであれば必見

国家資格である「基本情報技術者試験」にもアルゴリズムに関する問題が出てきますし、プログラムを始めるのであればこれぐらいのアルゴリズムは抑えておいた方がいいですね。

ちょっとパソコン関連に興味がある人であれば「なるほどね」とパズルの謎解き感覚で楽しめます。アルゴリズムって言葉の小難しさはまったくありません。

 

f:id:ok-alexa:20170311013511p:plain

ソートって何? それはエクセルでいう並び替えです。エクセルでは↑↓降順・昇順だけで並び替えられますが、その裏ではこんな処理をしてたんだ。って気づかされます。

 

約半分は無料で楽しめる

比較的理解しやすいアルゴリズムは無料で楽しめますが、難易度が高いものは有料です。「360円」*1のワンプライスで全アルゴリズムが表示されますので明快で分かりやすく、広告表示もないので好感が持てます。

 

f:id:ok-alexa:20170311021845p:plain

 

play.google.com

*1:2017/3/11現在の価格