とても長い配列の上位M件だけをクイックソートより高速に取り出す - Qiita

というわけで、10倍の差がでた。 当然、配列の長さやソートする長さ、また実装の方法によって性能差は変わってくるが 今回の方法は有効であるということは確認できた。 既存の記事(2015/11/09 20:22 追記) コメント欄でUnordered partial sorting にそれらしきことが書いてあると教えていただいた。 そちらでは、「上位k個を取り出す（ソートは不要）」という問題を考えている。 同様に分割統治法を用いてソートしていきながら、上位k個以内の小区間になったらその区間はソートせずに全て選択して良いとしている。 早い話が、QuickSelectによりk+1番目の要素を探してそれより上位の要素をごそっと抜き出している。 分割統治法で大雑把にソートしていきながら、不要なソートを行わないようにする という同様のアプローチである。 C++のSTLの場合(2015/11/09 22:

[sucrose]

昔ちょっと調べたけどクイックソート以外にもマージソートやヒープソート的なのでも部分ソートできるっぽい http://sucrose.hatenablog.com/entry/2013/11/05/235932

[tamaxyo]

ふむふむ

[Kureduki_Maari]

JavaScript - とても長い配列の上位M件だけをクイックソートより高速に取り出す by @Kiikurage on @Qiita

[tmatsuu]

おー知らなかった。なるほど。これパーセンタイルを算出するのにも使えるな。

[igrep]

“分割統治法でソートをしていく時に、分割された区間がそもそも上位M件にはいらなかったらその区間を無視する”

[hisasann]

配列

[Jxck]

なるほど

[clavier]

JavaScript - とても長い配列の上位M件だけをクイックソートより高速に取り出す - Qiita

[mattn]

面白い。

[wordi]

なるほどなあ

[naga_sawa]

Top-k アルゴリズム/そういえば一般的な Top-k ってどんな方法があるんだろう

[hatz48]

特定用途で重宝しそう