कॉम्ब सॉर्ट क्या है?
कॉम्ब सॉर्ट और बबल सॉर्ट का मूल विचार समान है। दूसरे शब्दों में, कॉम्ब सॉर्ट बबल सॉर्ट पर एक सुधार है। बबल सॉर्टिंग तकनीक में, आइटम्स की तुलना प्रत्येक चरण में अगले आइटम से की जाती है। लेकिन कॉम्ब सॉर्ट के लिए, आइटम्स को एक विशिष्ट गैप में सॉर्ट किया जाता है। प्रत्येक चरण को पूरा करने के बाद, गैप घटाया जाता है। इस सॉर्ट के लिए घटाने का फैक्टर या श्रिंक फैक्टर 1.3 है। इसका मतलब है कि प्रत्येक चरण को पूरा करने के बाद गैप को 1.3 से विभाजित किया जाता है।
जटिलता
- सर्वश्रेष्ठ स्थिति: O(n log n)
- औसत स्थिति: O(n²/2^p) जहां p इंक्रीमेंट की संख्या है
- सबसे खराब स्थिति: O(n²)
एल्गोरिदम
CombSort(array, size):
Begin
gap := size
flag := true
while gap != 1 OR flag == true:
gap = floor(gap / 1.3)
if gap < 1:
gap := 1
flag = false
for i = 0 to size - gap - 1:
if array[i] > array[i + gap]:
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; // श्रिंक फैक्टर 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);
return 0;
}
आउटपुट
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
गैप अनुक्रम उदाहरण (n=10)
10 → 7 → 5 → 3 → 2 → 1 → 1 → 1 ... (जब तक कोई स्वैप न हो)
कॉम्ब सॉर्ट बनाम बबल सॉर्ट
| पहलू | बबल सॉर्ट | कॉम्ब सॉर्ट |
|---|---|---|
| तुलना गैप | हमेशा 1 | श्रिंक फैक्टर 1.3 से घटता है |
| कछुआ समस्या | हां (छोटे तत्व धीरे-धीरे चलते हैं) | नहीं (बड़े गैप से कछुए तेजी से चलते हैं) |
| सर्वश्रेष्ठ स्थिति | O(n) | O(n log n) |
| औसत स्थिति | O(n²) | O(n²/2^p) |
श्रिंक फैक्टर 1.3 क्यों?
लेखकों (व्लादिमीर डोब्रीव और स्टीफन लेसी) ने अनुभवजन्य रूप से पाया कि 1.3 सबसे अच्छा प्रदर्शन देता है। 1.3 से कम → अधिक तुलनाएं, 1.3 से अधिक → कछुआ समस्या को प्रभावी ढंग से हल करने में विफल।