コムソート

1. コムソートアルゴリズム
2. コムソートの例
3. コムソートアルゴリズムの実装
4. コンブソートアルゴリズムの複雑さ

コムソートは単純な比較ベースのソートアルゴリズムです。これは、[バブルソート](/ja/tutorial/algorithm/bubble-sort/の改良版です。バブルソートでは、通過/相毎に隣接する要素を比較し、一つずつ反転を除去していきます。一方、コムソートでは、大きなギャップを利用して開始し、その都度 1.3 の縮率で縮小していきます。コムソートは、1 回のスワップだけで複数の反転を除去することができます。これはカメを殺すという発想に基づいています。タートルとはリストの最後にある小さな要素のことで、バブルソートの効率を低下させ、それを殺すことでソート性能を大幅に向上させます。

コムソートアルゴリズム

ここでは、n 要素を含むソートされていない配列 A[] があるとしましょう。ここでは、シュリンク係数を 1.3 とすることにします。

コムソートの例

配列 (3、5、2、8、1、7、6、4) があるとします。コムソートアルゴリズムを使用してソートします。

gap=8, swapped=true、SHRINK_FACTOR = 1.3 を初期化します。

• 最初のパス

gap = 8/1.3 = 6 , swapped = false.

• 2 回目のパス

gap = 6/1.3 = 4 , swapped = false.

• 3 回目のパス

gap= 4/1.3 = 3 , swapped = false.

• 4 回目のパス

gap = 3/1.3 = 2 , swapped = false.

• 5 回目のパス

gap = 2/1.3 = 1 , swapped = false.

最終的にソートされた配列は、 (1、2、3、4、5、6、7、8) として取得されます。

コムソートアルゴリズムの実装

#include <iostream>
using namespace std;

int updateGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  bool swapped = true;
  while (gap > 1 || swapped == true) {
    gap = updateGap(gap);
    swapped = false;
    for (int i = 0; i < (n - gap); i++) {
      int temp;
      if (arr[i] > arr[i + gap]) {
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  combSort(arr, n);
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

コンブソートアルゴリズムの複雑さ

時間計算量

• 平均のケース

時間の複雑さは [Big Theta]のオーダーです：O(n²/2^p) ここで、p はインクリメントの数です。

• 最悪のケース

最悪の場合の時間的複雑さは [Big O]です。O(n²)となります。

• 最良のケース

ベストケースは、配列が既にソートされているか、ほぼソートされている場合に発生します。最良の時間複雑度は [Big Omega]: O(nlogn) です。これは、バブルソートの最良の時間的複雑さを大幅に改善したものです。

空間計算量

このアルゴリズムの空間複雑度は O(n) です。これは櫛型ソートアルゴリズムが一時変数以外の空間を必要としないためです。