ソートアルゴリズム
「一番好きなソートアルゴリズムは何ですか？」
この質問に対する回答により、人間は以下のように分類することができます。
- クイックソート
- → 何をおいてもパフォーマンスだろ派
- マージソート
- → エレガントなアルゴリズムが好きです派
- 選択ソート
- → 簡単に書けるのがいいよ派
- ボゴソート
- → いくらなんでもひねくれすぎです。
……という冗談はさておき、今回は私が使用しているソート (クイックソートの変種) を紹介します。
1. 一般的なソートアルゴリズムの問題点
例えば、クイックソートが行う比較の回数は、要素数 n に対し O(nlogn) のオーダとなります。(最悪ケースでは O(n2) まで増加しますが、話の本筋とは関係ないので考慮には入れません。)
クイックソートに限らず、広く使用されているアルゴリズムでは、比較時に (必要であれば) 要素値の入れ換えも行います。
従って、要素値のコピー回数のオーダも、比較のそれと同じ O(nlogn) となります。
要素が構造体などデータサイズの大きいものである場合、このコピーにかかる処理コストはかなり大きくなります。
そこで、クイックソートを使いつつ、要素のコピー回数をできるだけ少なくする工夫をしてみました。