কম্ব সোর্ট বাবল সোর্টের উন্নত সংস্করণ। বাবল সোর্টে প্রতিটি ফেজে পরের এলিমেন্টের সাথে তুলনা হয়, কিন্তু কম্ব সোর্টে একটি নির্দিষ্ট গ্যাপ (gap) দিয়ে তুলনা হয়। প্রতিটি ফেজের পর গ্যাপ কমে যায়। شرিংক ফ্যাক্টর (shrink factor) ১.৩।
কম্ব সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: বেস্ট কেস O(n log n), এভারেজ O(n²/2^p), ওয়ার্স্ট O(n²)
- স্পেস কমপ্লেক্সিটি: 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)
Input: ডেটার অ্যারে, মোট এলিমেন্ট
Output: সর্ট করা অ্যারে
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
done
End
C++ উদাহরণ
#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; // shrink factor 1.3
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
