কম্ব সর্ট এবং বাবল সর্টের বেসিক আইডিয়া একই। অন্য কথায়, কম্ব সর্ট বাবল সর্টের একটি উন্নতি। বাবল সর্টিং টেকনিকলে, প্রতিটি ফেজে আইটেমগুলো পরবর্তী আইটেমের সাথে তুলনা করা হয়। কিন্তু কম্ব সর্টে, আইটেমগুলো একটি নির্দিষ্ট গ্যাপে সর্ট করা হয়। প্রতিটি ফেজ সম্পন্ন হলে, গ্যাপ কমে যায়। এই সর্টের ডিক্রিজিং ফ্যাক্টর বা শ্রিংক ফ্যাক্টর ১.৩। অর্থাৎ প্রতিটি ফেজের পর গ্যাপ ১.৩ দিয়ে ভাগ করা হয়। টাইম কমপ্লেক্সিটি বেস্ট কেসে O(n log n)। অয়ারেজ কেসে O(n²/2ⁿᴾ) (p হলো ইনক্রিমেন্টের সংখ্যা) এবং ওয়ার্স্ট কেসে O(n²)।
অ্যালগরিদম
CombSort(array, size)
ইনপুট - একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট - সর্টেড অ্যারে
Begin
gap := size
flag := true
while gap ≠ 1 OR flag = true do
gap = floor(gap/1.3) // ভাগফলের ফ্লোর ভ্যালু
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; // গ্যাপ সাইজ অ্যারে সাইজ দিয়ে ইনিশিয়ালাইজ
bool flag = true;
while(gap != 1 || flag == true){
gap = (gap*10)/13; // শ্রিংক ফ্যাক্টর দিয়ে গ্যাপ কমানো
if(gap < 1)
gap = 1;
flag = false;
for(int i = 0; i < size-gap; i++){ // গ্যাপ দিয়ে এলিমেন্ট তুলনা
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]; // দেয়া সংখ্যক এলিমেন্টে অ্যারে তৈরি
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
