कॉकटेल शेकर सॉर्ट

कॉकटेल शेकर सॉर्ट

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})\,$
Best-case performance	$O(n)\,$
Average performance	$O(n^{2})\,$
Worst-case space complexity	$O(1)$

कॉकटेल शेकर सॉर्ट, इसे द्विदिशात्मक बुलबुला सॉर्ट के रूप में भी जाना जाता है, कॉकटेल सॉर्ट, शेकर सॉर्ट (जो चयन सॉर्ट के प्रकार को भी संदर्भित कर सकता है), रिपल सॉर्ट, शफ़ल सॉर्ट, या शटल सॉर्ट, बुलबुले की तरह का विस्तार है। एल्गोरिदम दो दिशाओं में काम करके बबल सॉर्ट का विस्तार करता है। हालाँकि यह अधिक बबल सॉर्ट#खरगोशों और कछुओं द्वारा बबल सॉर्ट में सुधार करता है, लेकिन यह केवल मामूली प्रदर्शन सुधार प्रदान करता है।

बबल सॉर्ट के अधिकांश प्रकारों की तरह, कॉकटेल शेकर सॉर्ट का उपयोग मुख्य रूप से शैक्षिक उपकरण के रूप में किया जाता है। जल्दी से सुलझाएं, मर्ज़ सॉर्ट या टाइमसॉर्ट जैसे अधिक प्रदर्शन करने वाले एल्गोरिदम का उपयोग पायथन और जावा जैसी लोकप्रिय प्रोग्रामिंग भाषाओं में निर्मित सॉर्टिंग लाइब्रेरी द्वारा किया जाता है।

छद्मकोड

हर बार पूरी सूची में सबसे सरल फ़ॉर्म डाला जाता है:

प्रक्रिया कॉकटेलशेकरसॉर्ट(ए: क्रमबद्ध वस्तुओं की सूची) है
    करना
        अदला-बदली:=झूठा
        0 से लंबाई (ए) - 1 में प्रत्येक i के लिए करें:
            यदि A[i] > A[i + 1] तो // परीक्षण करें कि क्या दोनों तत्व गलत क्रम में हैं
                स्वैप(ए[आई], ए[आई + 1]) // दो तत्वों को स्थान बदलने दें
                अदला-बदली := सत्य
            अगर अंत
        के लिए समाप्त
        अगर अदला-बदली नहीं हुई तो
            // यदि कोई स्वैप नहीं हुआ तो हम यहां बाहरी लूप से बाहर निकल सकते हैं।
            डू-व्हाइल लूप को तोड़ें
        अगर अंत
        अदला-बदली:=झूठा
        लंबाई (ए) - 1 से 0 में प्रत्येक i के लिए करें:
            यदि A[i] > A[i + 1] तो
                स्वैप(ए[आई], ए[आई + 1])
                अदला-बदली := सत्य
            अगर अंत
        के लिए समाप्त
    स्वैप करते समय // यदि कोई तत्व स्वैप नहीं किया गया है, तो सूची क्रमबद्ध की गई है
अंतिम प्रक्रिया

पहला दाहिनी ओर वाला पास सबसे बड़े तत्व को अंत में उसके सही स्थान पर स्थानांतरित कर देगा, और निम्नलिखित बाईं ओर वाला पास सबसे छोटे तत्व को शुरुआत में उसके सही स्थान पर स्थानांतरित कर देगा। दूसरा पूर्ण पास दूसरे सबसे बड़े और दूसरे सबसे छोटे तत्वों को उनके सही स्थानों पर स्थानांतरित कर देगा, इत्यादि। i पास होने के बाद, सूची में पहला i और अंतिम i तत्व अपनी सही स्थिति में हैं, और उन्हें जाँचने की आवश्यकता नहीं है। हर बार क्रमबद्ध की जाने वाली सूची के हिस्से को छोटा करके, संचालन की संख्या आधी की जा सकती है (बबल_सॉर्ट#वैकल्पिक_क्रियान्वयन देखें)।

यह MATLAB/OCTAVE में अंतिम स्वैप इंडेक्स को याद रखने और सीमाओं को अपडेट करने के अनुकूलन के साथ एल्गोरिदम का उदाहरण है।

function A = cocktailShakerSort(A)
% `beginIdx` and `endIdx` marks the first and last index to check
beginIdx = 1;
endIdx = length(A) - 1;
while beginIdx <= endIdx
    newBeginIdx = endIdx;
    newEndIdx = beginIdx;
    for ii = beginIdx:endIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newEndIdx = ii;
        end
    end

    % decreases `endIdx` because the elements after `newEndIdx` are in correct order
    endIdx = newEndIdx - 1;

    for ii = endIdx:-1:beginIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newBeginIdx = ii;
        end
    end
    % increases `beginIdx` because the elements before `newBeginIdx` are in correct order
    beginIdx = newBeginIdx + 1;
end
end

बबल सॉर्ट से अंतर

कॉकटेल शेकर सॉर्ट, बबल सॉर्ट का थोड़ा सा बदलाव है।इसमें अंतर यह है कि सूची में बार-बार नीचे से ऊपर की ओर जाने के बजाय, यह बारी-बारी से नीचे से ऊपर और फिर ऊपर से नीचे की ओर गुजरती है। यह मानक बबल सॉर्ट की तुलना में थोड़ा बेहतर प्रदर्शन प्राप्त कर सकता है। इसका कारण यह है कि बबल सॉर्ट सूची से केवल दिशा में गुजरता है और इसलिए प्रत्येक पुनरावृत्ति में आइटम को केवल कदम पीछे ले जाया जा सकता है।

इस बिंदु को साबित करने वाली सूची का उदाहरण सूची (2,3,4,5,1) है, जिसे क्रमबद्ध होने के लिए केवल कॉकटेल सॉर्ट के पास से गुजरना होगा, लेकिन यदि आरोही बबल सॉर्ट का उपयोग किया जाए तो चार की आवश्यकता होगी गुजरता। हालाँकि कॉकटेल सॉर्ट पास को दो बबल सॉर्ट पास के रूप में गिना जाना चाहिए। आमतौर पर कॉकटेल सॉर्ट, बबल सॉर्ट की तुलना में दो गुना से भी कम तेज़ होता है।

एक और अनुकूलन यह हो सकता है कि एल्गोरिदम याद रखे कि अंतिम वास्तविक स्वैप कहां किया गया है। अगले पुनरावृत्ति में, इस सीमा से अधिक कोई स्वैप नहीं होगा और एल्गोरिदम में छोटे पास होंगे। चूंकि कॉकटेल शेकर सॉर्ट द्विदिश रूप से होता है, संभावित स्वैप की सीमा, जो कि परीक्षण की जाने वाली सीमा है, प्रति पास कम हो जाएगी, इस प्रकार कुल चलने का समय थोड़ा कम हो जाएगा।

जटिलता

बड़ा ओ अंकन में कॉकटेल शेकर सॉर्ट की जटिलता है $O(n^{2})$ सबसे खराब स्थिति और औसत स्थिति दोनों के लिए, लेकिन यह करीब हो जाता है $O(n)$ यदि सूची को अधिकतर सॉर्टिंग एल्गोरिदम लागू करने से पहले ऑर्डर किया गया है। उदाहरण के लिए, यदि प्रत्येक तत्व ऐसी स्थिति में है जो उस स्थिति से अधिकतम k (k ≥ 1) भिन्न है, जहां वह समाप्त होने वाला है, तो कॉकटेल शेकर सॉर्ट की जटिलता बन जाती है $O(kn).$ बबल सॉर्ट के समान परिशोधन के साथ, कंप्यूटर प्रोग्रामिंग की कला पुस्तक में कॉकटेल शेकर सॉर्ट की भी संक्षेप में चर्चा की गई है। अंत में, नुथ बबल सॉर्ट और उसके सुधारों के बारे में बताते हैं:

But none of these refinements leads to an algorithm better than straight insertion [that is, insertion sort]; and we already know that straight insertion isn't suitable for large N. [...] In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.

— D. E. Knuth

स्रोत

• Hartenstein, R. (July 2010). "कंप्यूटिंग का एक नया विश्व मॉडल" (PDF). The Grand Challenge to Reinvent Computing. Belo Horizonte, Brazil: CSBC. Archived from the original (PDF) on 2013-08-07. Retrieved 2011-01-14.

बाहरी संबंध

• Interactive demo of cocktail sort
• Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
• ".NET Implementation of cocktail sort and several other algorithms". Archived from the original on 2012-02-12.