コームソート

コームソート

縮小係数k =1.24733のコームソート
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$[1]
最高の パフォーマンス	${\displaystyle \Theta (n\log n)}$
平均的 なパフォーマンス	${\displaystyle \オメガ (n^{2}/2^{p})}$ここでpは増分数である[1]
最悪の場合の 空間複雑度	${\displaystyle O(1)}$

コームソートは、もともと1980年にWłodzimierz DobosiewiczとArtur Borowyによって設計された比較的単純なソートアルゴリズムであり、 ^{[1] [2]}その後1991年にStephen LaceyとRichard Boxによって再発見され、「コームソート」という名前が付けられました。^[3]コームソートは、シェルソートが挿入ソートを改良したのと同じようにバブルソートを改良しており、どちらも意図した位置から遠く離れた場所から始まる要素を1回のスワップで1つ以上のスペースに移動できます。

nist.govの「漸増ソート」の定義では、「櫛の歯が触れる」データの反復パスを視覚化するものとして「櫛ソート」という用語が言及されており、前者の用語はドン・クヌースにリンクされています。 ^[4]

基本的な考え方は、タートル(リストの末尾近くにある小さな値) を削除することです。バブル ソートでは、これらによってソートの速度が大幅に低下するためです。ウサギ (リストの先頭付近にある大きな値) は、バブル ソートでは問題になりません。

バブルソートでは、任意の2つの要素を比較すると、それらのギャップ（互いの距離）は常に1になります。 ^[5]コームソートの基本的な考え方は、ギャップが1よりもはるかに大きくなる可能性があるということです。実際のスワップを実行するバブルソートの内側のループは、スワップされた要素間のギャップが（外側のループの各反復ごとに）「縮小係数」 kのステップで減少するように変更されます。[ ⁠ん/け⁠、⁠ん/2 ^...⁠、⁠ん/3 ³⁠、...、1]。

ギャップは、ソートするリストの長さnを縮小係数k (通常は 1.3、下記参照) で割った値から始まり、そのギャップで前述の修正バブル ソートの 1 回のパスが適用されます。次に、ギャップが再び縮小係数で割られ、リストがこの新しいギャップでソートされ、ギャップが 1 になるまでこのプロセスが繰り返されます。この時点で、リストが完全にソートされるまで、ギャップ 1 を使用してコーム ソートが続行されます。ソートの最終段階はバブル ソートと同等ですが、この時点でほとんどのタートルが処理されているため、バブル ソートの方が効率的です。

縮小係数は、コームソートの効率に大きく影響します。Dobosiewicz はk = 4/3 = 1.333… を提案しましたが、Lacey と Box は、長さが約 1000 の 200,000 を超えるランダム リストで実験的にテストした結果、理想的な縮小係数として 1.3 を提案しました。値が小さすぎると、不必要に多くの比較を行ってアルゴリズムの速度が低下しますが、値が大きすぎると、タートルを効果的に処理できず、ギャップ 1 のパスが多数必要になります。

ギャップが減少するソート パスを繰り返すパターンは Shellsort に似ていますが、Shellsort では、配列は各パスで完全にソートされてから、次に小さいギャップに進みます。コーム ソートのパスでは、要素は完全にソートされません。これが、Shellsort ギャップ シーケンスの最適な縮小係数が約 2.25 と大きい理由です。

Lacey と Box が提案したもう 1 つの改良点は、「11 のルール」です。これは、ギャップ サイズを常に 11 にして、ギャップ サイズ 9 または 10 (ギャップ 12、13、または 14 を 1.3 で割った値) を 11 に切り上げるというものです。これにより、最後のギャップ 1 パスまで生き残るカメが排除されます。

関数combsort(配列入力)は

    gap := input.size // ギャップサイズを初期化する
    shrink := 1.3 // ギャップの縮小係数を設定する
    ソート済み := false

    loop while sorted = false
         // 次のコームのギャップ値を更新
        ギャップ := フロア(ギャップ / 収縮)
        ギャップ≤1の場合
            ギャップ := 1
            sorted := true // このパスでスワップがない場合は終了、
        そうでない場合はgap = 9またはgap = 10の場合は
            gap := 11       // 「11 のルール」
        終了 if

        // 入力リストを 1 回「コーム」する
        私 := 0
        loop while i + gap < input.size //同様のアイデアについてはShell sortを
            参照してください。if input[i] > input[i+gap] then swap (input[i], input[i+gap])
                
                ソート済み := false
                // この割り当てがループ内で発生しない場合は、
                // スワップは行われず、リストはソートされます
             。
    
             私 := 私 + 1
         ループ終了
     ループ終了 関数
終了

Wikibookのアルゴリズム実装には、くし形ソートに関するページがあります。

• バブル ソートは、一般的に遅いアルゴリズムであり、コーム ソートの基礎となります。
• カクテルソート、または双方向バブルソートは、バブルソートのバリエーションであり、効果は劣るものの、タートル問題にも対処します。