ソート機能の使い分け、応用

[lempiji]

遺伝的アルゴリズムや各種シミュレーションでちょいちょい出てくる記述を整理しておきたいです。

• 上位N個が分かれば良いので効率よくソートしたい（topN）
  • (配列の長さ/2+1)個をソートすれば中央値が求められる、などの応用
• 重い評価/比較関数を使ったソートを高速化したい（schwartzSort）
• 複数の配列を1つとみなしてソートしたい（chain, completeSort）
• 複数のキーを条件にソートしたい（multiSort）
• 要素が const や immutable の配列を並び替えたい（.dup するか makeIndex で順位を表す配列を作る）

[shoo]

そういえばちょっと前にクイックソートの計算量が話題になりましたね。

データ件数、コンテナの構造、比較関数の重さ、安定ソートが必要か、ソート前のデータの整列度合いなどで最適なアルゴリズムが変わるので、ソートアルゴリズムの選定は難しいですよね。