クイックソート殺し - 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++ の
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
秋元@サイボウズラボ・プログラマー・ブログ: 各ソート技法をアニメーションで表示するAnimated Sorting Algorithm Demo
ソートアルゴリズムのアニメーションデモでは、様々なソート手法(挿入、選択、バブル、シェル、マージ、ヒープ、クイック、三分割クイック)について、ソート対象のデータが完全ランダムの場合、ほぼソートされている状態、逆順にソート […] ソートアルゴリズムのアニメーションデモでは、様々なソート手法(挿入、選択、バブル、シェル、マージ、ヒープ、クイック、三分割クイック)について、ソート対象のデータが完全ランダムの場合、ほぼソートされている状態、逆順にソートされている場合、同じ値のものが多数ある場合のデータをソートする様子を、Javascriptを使ったアニメーションで見せてくれる。 それぞれのソートアルゴリズムがどのようなものか見せるというだけでなく、ソートのアルゴリズムに「常にこれが最適」というものはない、というのを示すのも目的、ということだ。 各アルゴリズムのリンクからは、そのアルゴリズムのコー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
502 Bad Gateway
