कॉकटेल सॉर्ट क्या है?
कॉकटेल सॉर्ट बबल सॉर्ट का एक और प्रकार है। बबल सॉर्ट तकनीक में, यह हमेशा बाएं से दाएं खोजता है, और अंत में सबसे बड़ा तत्व ढूंढता है, दूसरे चरण में यह दूसरा सबसे बड़ा तत्व दूसरे अंतिम स्थान पर ढूंढता है। यह सॉर्टिंग तकनीक वैकल्पिक रूप से दोनों दिशाओं में पार करती है।
एल्गोरिदम
cocktail(array, n):
Begin
flag := true
start := 0, end := n-1
while flag is set:
flag := false
for i in range start to end-1:
if arr[i] > arr[i+1]:
exchange arr[i] and arr[i+1]
flag := true
end if
done
if flag is not set:
break
end if
flag := false
end := end - 1
for i in range end-1 down to start:
if arr[i] > arr[i+1]:
exchange arr[i] and arr[i+1]
flag := true
end if
done
start := start + 1
done
End
उदाहरण
#include <iostream>
#include <algorithm>
using namespace std;
void cocktailSort(int arr[], int n) {
bool flag = true;
int start = 0, end = n - 1;
while(flag) {
flag = false;
// बाएं से दाएं (बबल सॉर्ट की तरह)
for(int i = start; i < end; i++) {
if(arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]);
flag = true;
}
}
if(!flag) {
break; // यदि कुछ नहीं बदला, तो लूप तोड़ें
}
flag = false;
end--; // अंत पॉइंटर घटाएं
// दाएं से बाएं
for(int i = end - 1; i >= start; i--) {
if(arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]);
flag = true;
}
}
start++;
}
}
int main() {
int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
int n = sizeof(data) / sizeof(data[0]);
cout << "Sorted Sequence: ";
cocktailSort(data, n);
for(int i = 0; i < n; i++) {
cout << data[i] << " ";
}
cout << endl;
return 0;
}
आउटपुट
Sorted Sequence 13 20 32 35 40 54 74 98 98 154
कैसे काम करता है (चरण-दर-चरण)
प्रारंभिक: [54, 74, 98, 154, 98, 32, 20, 13, 35, 40]
पास 1 (फॉरवर्ड): सबसे बड़ा 154 अंत में जाता है
[54, 74, 98, 98, 32, 20, 13, 35, 40, 154]
पास 1 (बैकवर्ड): सबसे छोटा 13 शुरुआत में जाता है
[13, 54, 74, 98, 98, 32, 20, 35, 40, 154]
पास 2 (फॉरवर्ड): अगला सबसे बड़ा 98...
[13, 54, 74, 98, 32, 20, 35, 40, 98, 154]
पास 2 (बैकवर्ड): अगला सबसे छोटा 20...
[13, 20, 54, 74, 98, 32, 35, 40, 98, 154]
... जारी रहता है जब तक सॉर्ट न हो जाए
जटिलता विश्लेषण
| स्थिति |
समय जटिलता |
स्थान जटिलता |
| सर्वश्रेष्ठ |
O(n) |
O(1) |
| औसत |
O(n²) |
O(1) |
| सबसे खराब |
O(n²) |
O(1) |
कॉकटेल सॉर्ट बनाम बबल सॉर्ट
| विशेषता |
बबल सॉर्ट |
कॉकटेल सॉर्ट |
| दिशा |
एक दिशा (बाएं→दाएं) |
द्विदिशात्मक |
| कछुआ समस्या |
हां |
आंशिक रूप से हल |
| सर्वश्रेष्ठ स्थिति |
O(n) |
O(n) |
| स्थिरता |
स्थिर |
स्थिर |
अन्य नाम
- द्विदिशात्मक बबल सॉर्ट
- कॉकटेल शेकर सॉर्ट
- शेकर सॉर्ट
- रिपल सॉर्ट
- शटल सॉर्ट