コムソート

Harshit Jindal 2023年10月12日
  1. コムソートアルゴリズム
  2. コムソートの例
  3. コムソートアルゴリズムの実装
  4. コンブソートアルゴリズムの複雑さ
コムソート

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

コムソートアルゴリズム

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

  • 変数 gap を配列のサイズ、変数 swappedtrue として初期化します。
  • 定数変数 SHRINK_FACTOR1.3 と宣言します。
  • gap が 1 でない場合や swappedtrue に設定されている場合は、以下のようにします。
    • Set swapped as false.
    • Set gap as (int)gap/SHRINK_FACTOR.
    • For every element in the range 0 to n - gap do the following - if A[i] > A[i+gap]swap(A[i], A[i+gap]) and set swapped to true.

コムソートの例

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

gap=8, swapped=trueSHRINK_FACTOR = 1.3 を初期化します。

  • 最初のパス

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

反復 (3, 5, 2, 8, 1, 7, 6, 4) アクション
i = 0 (3, 5, 2, 8, 3, 7, 6, 4) 3 < 6、スワップなし
i = 1 (3, 4, 2, 8, 1, 7, 6, 5) 5 > 4, スワップ
  • 2 回目のパス

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

反復 (3, 4, 2, 8, 1, 7, 6, 5) アクション
i = 0 (1, 4, 2, 8, 3, 7, 6, 5) 3 > 1, スワップ
i = 1 (1, 4, 2, 8, 3, 7, 6, 5) 4 < 7、スワップなし
i = 2 (1, 4, 2, 8, 3, 7, 6, 5) 2 < 6, スワップなし
i = 3 (1, 4, 2, 5, 3, 7, 6, 8) 8 > 5, スワップ
  • 3 回目のパス

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

反復 (1, 4, 2, 5, 3, 7, 6, 8) アクション
i = 0 (1, 4, 2, 5, 3, 7, 6, 8) 1 < 5, スワップなし
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 4 > 3, スワップ
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2 < 7, スワップなし
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5 < 6、スワップなし
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4 < 8, スワップなし
  • 4 回目のパス

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

反復 (1, 3, 2, 5, 4, 7, 6, 8) アクション
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1 < 2、スワップなし
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 3 < 5, スワップなし
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2 < 4, スワップなし
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5 < 7, スワップなし
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4 < 6、スワップなし
i = 5 (1, 3, 2, 5, 4, 7, 6, 8) 7 < 8, スワップなし
  • 5 回目のパス

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

反復 (1, 3, 2, 5, 4, 7, 6, 8) アクション
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1 < 3、スワップなし
i = 1 (1, 2, 3, 5, 4, 7, 6, 8) 3 > 2, スワップ
i = 2 (1, 2, 3, 5, 4, 7, 6, 8) 3 < 5, スワップなし
i = 3 (1, 2, 3, 4, 5, 7, 6, 8) 5 > 4, スワップ
i = 4 (1, 2, 3, 4, 5, 7, 6, 8) 5 < 7, スワップなし
i = 5 (1, 2, 3, 5, 4, 6, 7, 8) 7 > 6, スワップ
i = 6 (1, 2, 3, 4, 5, 6, 7, 8) 7 < 8, スワップなし

最終的にソートされた配列は、 (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(n2/2p) ここで、p はインクリメントの数です。

  • 最悪のケース

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

  • 最良のケース

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

空間計算量

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

著者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

関連記事 - Sort Algorithm