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

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

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)$

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

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

स्यूडोकोड

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

procedure cocktailShakerSort(A : list of sortable items) is
    do
        swapped := false
        for each i in 0 to length(A) − 1 do:                                                                
            if A[i] > A[i + 1] then // test whether the two elements are in the wrong order
                swap(A[i], A[i + 1]) // let the two elements change places                                      
                swapped := true                                                                      
            end if                                                                                           
        end for
        if not swapped then
            // we can exit the outer loop here if no swaps occurred.                                                    
            break do-while loop                                                                                 
        end if                                                                                                      
        swapped := false
        for each i in length(A) − 1 to 0 do:
            if A[i] > A[i + 1] then
                swap(A[i], A[i + 1])
                swapped := true
            end if
        end for
    while swapped // if no elements have been swapped, then the list is sorted
end procedure

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

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

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).$ बन जाती है बबल सॉर्ट के समान परिशोधन के साथ, कंप्यूटर प्रोग्रामिंग आर्ट पुस्तक में कॉकटेल शेकर सॉर्ट की भी संक्षेप में चर्चा की गई है। इस प्रकार अंत में, नुथ बबल सॉर्ट और उसके सुधारों के बारे में बताते हैं:

किन्तु इनमें से कोई भी परिशोधन सीधे सम्मिलन से उत्तम एल्गोरिदम की ओर नहीं ले जाता है [अर्थात, प्रविष्ट सॉर्ट]; और हम पहले से ही जानते हैं कि सीधी प्रविष्टि बड़े N के लिए उपयुक्त नहीं है। [...] संक्षेप में, ऐसा लगता है कि बबल सॉर्ट के पास इसकी अनुशंसा करने के लिए कुछ भी नहीं है, अतिरिक्त एक आकर्षक नाम और इस तथ्य के कि यह कुछ रोचक सैद्धांतिक समस्याओं को जन्म देता है।

— डी. ई. नुथ

स्रोत

• 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.