コムソート

コムソート手法の複雑さ

• 時間計算量： 最良の場合はO（n log n）。平均的な場合はO（n ^ 2/2 ^ p）（pは増分の数）、最悪の場合はO（n ^ 2）です。
• スペースの複雑さ： O（1）

入力と出力

Input:
A list of unsorted data: 108 96 23 74 12 56 85 42 13 47
Output:
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108

アルゴリズム

CombSort(array, size)

入力- データの配列、および配列内の総数

出力- ソートされた配列

Begin
   gap := size
   flag := true
   while the gap ≠ 1 OR flag = true do
      gap = floor(gap/1.3) //the the floor value after division
      if gap < 1 then
         gap := 1
      flag = false

      for i := 0 to size – gap -1 do
         if array[i] > array[i+gap] then
            swap array[i] with array[i+gap]
            flag = true;
      done
   done
End

例

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void combSort(int *array, int size) {
   int gap = size; //initialize gap size with size of array
   bool flag = true;

   while(gap != 1 || flag == true) {
      gap = (gap*10)/13; //minimize gap by shrink factor
      if(gap<1)
         gap = 1;
      flag = false;

      for(int i = 0; i<size-gap; i++) { //compare elements with gap
         if(array[i] > array[i+gap]) {
            swap(array[i], array[i+gap]);
            flag = true;
         }
      }
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; //create an array with given number of elements
   cout << "Enter elements:" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   combSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

出力

Enter the number of elements: 10
Enter elements:
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108