コムソート用のC++プログラム？

コムソートとバブルソートの基本的な考え方は同じです。言い換えれば、コムソートはバブルソートの改良です。バブルソート手法では、各フェーズでアイテムが次のアイテムと比較されます。ただし、コムソートの場合、アイテムは特定のギャップでソートされます。各フェーズが完了すると、ギャップが減少します。この種の減少係数または縮小係数は1.3です。これは、各フェーズを完了した後、ギャップが1.3で除算されることを意味します。最良の場合、時間計算量はO（n log n）です。 O（n ² / 2n ^P ）（pは増分の数）平均的な場合とO（n ² ）最悪の場合。

アルゴリズム

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