कंघी सॉर्ट और बबल सॉर्ट का मूल विचार समान है। दूसरे शब्दों में, कंघी सॉर्ट बबल सॉर्ट पर एक सुधार है। बबल छँटाई तकनीक में, वस्तुओं की तुलना प्रत्येक चरण में अगले आइटम से की जाती है। लेकिन कंघी प्रकार के लिए, वस्तुओं को एक विशिष्ट अंतराल में क्रमबद्ध किया जाता है। प्रत्येक चरण को पूरा करने के बाद, अंतर कम हो जाता है। इस प्रकार का ह्रासमान कारक या सिकुड़न कारक 1.3 है। इसका मतलब है कि प्रत्येक चरण को पूरा करने के बाद अंतराल को 1.3 से विभाजित किया जाता है। सर्वोत्तम मामले के लिए समय जटिलता ओ (एन लॉग एन) है। ओ(एन 2 /2n P ) (p वेतन वृद्धि की संख्या है) औसत मामले के लिए और O(n 2 ) सबसे खराब स्थिति के लिए।
एल्गोरिदम
CombSort(सरणी, आकार)
इनपुट - डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट - क्रमबद्ध सरणी
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