【Unity】ソートアルゴリズム12種を可視化してみた - Qiita
はじめに ソートアルゴリズムの学習として、12種のソートアルゴリズムを実装して可視化してみました。 Unityにはあまり関係がなさそうな話題ですが、Unity上で作ったのでUnityタグをつけます。 バブルソート バブルソートのアルゴリズムは以下のような感じです。 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える 全ての要素の順序が正しくなるまで 1.を繰り返す. void BubbleSort(int[] a) { bool isEnd = false; int finAdjust = 1; // 最終添え字の調整値 while (!isEnd) { bool loopSwap = false; for (int i = 0; i < a.Length - finAdjust; i++) { if (a[i] < a[i + 1]) { Swap(ref a[i],
d.y.d.
22:43 21/11/09 ヒープソートが好きである ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…！という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか
ソートアルゴリズム高速化への道 - kivantium活動日記
先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
クイックソート殺し - d.y.d.
19:39 12/09/01 クイックソート殺し こういう系統の話。 Quicksort Killer (kazoo04さん) qsortを撃墜し(最悪ケースを与え)てみた。 (qnighyさん) A Killer Adversary for Quicksort (shinhさんの解説) Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (徳丸さんの解説) ただのクイックソートは要素数 N の配列をソートするのに最悪 N2 オーダの時間がかかってしまう、 そしてそれは pivot を偏って選びまくってしまった時に発生する、というのはよく知られた話だと思います。 といっても、広く使われている言語／ライブラリのソート関数はその辺り気をつけられていて、最悪時も O(N log N) になるアルゴリズムで実装されている…と思い込んでいたのですが（例えば C++ の
第12回アルゴリズム勉強会に行ってきました - アスペ日記
人生初勉強会。 やったのは counting sort と radix sort。 この二つは書いたことがなかったので、Python で超手抜きに書いてみた。 https://gist.github.com/1395308 base = 10 def radix_sort(x, max): radix = 1 while radix < max: x = counting_sort(x, radix) radix *= base return x def counting_sort(a, radix): c = [0] * base for k in a: r = (k / radix) % base c[r] += 1 for i in range(1, base): c[i] += c[i - 1] b = [0] * len(a) for k in reversed(a): r =
シェルソート - Wikipedia
間隔5, 3, 1のシェルソートにおける要素の交換を示した図 シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発した[2]ソートのアルゴリズム。挿入ソートの一般化[3]であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。 アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿
バブルソートの遅さを体感してみる - yarbの日記
バブルソートには思い出がある。大学生のときにPC-9801で落ちゲーを作った。上から落ちてくるトランプのカードを5×5のマトリックスに積み上げて、縦横斜めでポーカーの役を作る。やりこむと「縦列で数字を揃えようとしても最後で失敗する確率が高くてスコアの期待値は低い。むしろ横のフラッシュを多く目指せ。フラッシュ作りは一気にやらないと失敗のペナルティが高すぎる」というような経験則が蓄積していく楽しいゲームだった。いまでもやりたいぐらい。たぶんオリジナルは「琉球」という名前のアーケードゲームだった。 そのとき、ポーカーの役判定のロジックを書き下ろしたときにやったのが、バブルソートだということを、かなり後になってから知った。当時はソートという言葉すら知らなかった。 カードは最大で5枚だし、チェックすべき列も1度に最大4列だから、どんなにひどいことをやっても処理時間はかからないということは分かっていた
連結リストのソート - yarbの日記
C入門、プログラミング入門として、連結リストの次に基本的なソートをやってみようと少し格闘してみた。単純なint配列とかじゃテキストのままなので、どうせだったら連結リストを並べ変えてみようと思ったのが間違いだった。 まず、いちばん簡単なのは隣り合うノードを入れ替えるswap関数を作ることかと思った。ある世代以降のCでは構造体同士の代入ができるらしいので、もしかしてポインタ入れ替えよりも、ごそっとデータを入れ替えるのが正解なのかと一瞬思ったけど、さすがにそれじゃリストの意味がない。 ともあれ、swap関数さえあれば、後はリストを順にたぐりつつ入れ替えればバブルソートはすぐできるはず。でも、考えてみると、2個のノードを入れ替えるといってもそれらが隣接するノードとの配線もあるので、どうも単純じゃない。しかも、先頭はlist->headと特殊なポインタで参照されていたり、最後はNULLで終わっていた
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
Robert Sedgewick - Robert Sedgewick
Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton University. He was a member of the board of directors of Adobe Systems from 1990 to 2016, served on the faculty at Brown University from 1975 to 1985, and has held visiting research positions at Xerox PARC, IDA, and INRIA. His research expertise is in algorithm science, data
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
QDくん⚡️Python x 機械学習 x 金融工学 on Twitter: "ソートアルゴリズムの計算量の違いをわかりやすく可視化した記事 【Unity】ソートアルゴリズム12種を可視化してみた https://t.co/SBT4Xo42ku https://t.co/Cv7GfOvAF2"
並列化による高速化
【またかよ】「Haskellでクイックソート」問題【何度目だ】