ソートアルゴリズム

「一番好きなソートアルゴリズムは何ですか？」
この質問に対する回答により、人間は以下のように分類することができます。

クイックソート: → 何をおいてもパフォーマンスだろ派
マージソート: → エレガントなアルゴリズムが好きです派
選択ソート: → 簡単に書けるのがいいよ派
ボゴソート: → いくらなんでもひねくれすぎです。

……という冗談はさておき、今回は私が使用しているソート (クイックソートの変種) を紹介します。

1. 一般的なソートアルゴリズムの問題点

例えば、クイックソートが行う比較の回数は、要素数 n に対し O(nlogn) のオーダとなります。(最悪ケースでは O(n²) まで増加しますが、話の本筋とは関係ないので考慮には入れません。)
クイックソートに限らず、広く使用されているアルゴリズムでは、比較時に (必要であれば) 要素値の入れ換えも行います。従って、要素値のコピー回数のオーダも、比較のそれと同じ O(nlogn) となります。要素が構造体などデータサイズの大きいものである場合、このコピーにかかる処理コストはかなり大きくなります。

そこで、クイックソートを使いつつ、要素のコピー回数をできるだけ少なくする工夫をしてみました。

2. インデクス配列

例として、Fig a-1 の配列をソートすることにします。

まず、配列と同じサイズの「インデクス配列」を作成します。
インデクス配列の要素は、もとの配列の要素と一対一に対応します。

Fig 1-b: インデクス配列の作成

このインデクス配列に対して通常のソートアルゴリズム (クイックソート) を適用します。
ただし、比較処理は要素値 (インデクス) の大小関係ではなく、それが示すもとの配列の要素値によって行います。
例えば、要素 [3] と [5] の比較・置換は下図のようになります。

Fig. 1-c: インデクス配列のソート (比較)

Fig. 1-d: インデクス配列のソート (置換)

こうしてソートされたインデクス配列は、もとの配列の要素をそれぞれどこへ移動すればよいかを示すことになります。

Fig 1-e: ソートされたインデクス配列

 が示す要素の移動方法は次の通りとなります。

(図中の矢印とは逆向きとなっていることに注意してください。)


←'a',
←'g',
←'h',
…
←'r',
←'t'




3. 要素の移動




いよいよインデクス配列に従って実際に要素を移動させます。

要素を先頭から順にただコピーしてしまうと、コピー前の要素が上書きされてしまい上手くいきません。


要素が移動する道筋に注目してみると、いくつかの「循環」があることがわかります。

今回の例では３つの循環があるので、これらをそれぞれ α, β, γ としましょう。


Fig 1-f: 循環 α (長さ 1)




Fig 1-g: 循環 β (長さ 4)




Fig 1-h: 循環 γ (長さ 4)




要素の移動は、これらの循環ごとに分けて行わなければなりません。

また、循環の視点にある要素の値を格納するバッファが必要となります。


循環 α:
    長さが１なので、要素を移動させる必要はありません。
循環 β:
    次の手順で要素の移動を行います。

    バッファに [1] の値 'l' をコピー
    [1] に [2] の値 'g' をコピー
    [2] に [7] の値 'h' をコピー
    [7] に [4] の値 'r' をコピー
    [4] に バッファから 'l' をコピー

    循環 γ:
    循環 β と同様の手順で要素の移動を行います。

    バッファに [3] の値 'o' をコピー
    [3] に [5] の値 'i' をコピー
    [5] に [8] の値 'm' をコピー
    [8] に [6] の値 't' をコピー
    [6] に バッファから 'o' をコピー



これですべての要素を正しい位置に移動させることができました。


Fig 1-i: 要素の移動完了






4. パフォーマンス考察




実際のところ、このアルゴリズムで要素コピーの回数はどれくらい減るのでしょうか？


最良のケースは、要素が全く移動しない場合、即ち配列がソート済みの状態だったときです。

このとき、コピーは一度も行われません。(クイックソートでも同様です。)
ちなみに、その次に良いケースは循環が 1つだけの場合です。

このときのコピー回数は n + 1 となります。


最悪のケースは、全ての循環が長さ 2 (要素数が奇数の場合は、長さ 1の循環がひとつだけできる) の場合です。

このとき、発生する循環の個数は n/2 であり、循環あたりのコピー回数は 3となるので、全体でのコピー回数は 3n/2 となります。


このアルゴリズムは、最悪のケースに対してもコピーの回数は O(n) のオーダで済みます。

これは理論的な最小値でもあり、コピー回数をこれより抑えることは (現在のコンピュータでは) できません。


ただし、インデクス配列を生成, ソートする際にインデクス値 (一般に 4バイト) のコピーが発生するため、int, double などの配列に対してはクイックソートよりも効率が落ちることになります。

要素サイズが大きい場合のみ威力を発揮するという点に注意が必要です。





担当: 成田