View source for कॉकटेल शेकर सॉर्ट

{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=[[File:Sorting shaker sort anim.gif|Visualization of shaker sort]]
|data=[[Array data structure|Array]]
|best-time= <math>O(n)\,</math>
|average-time= <math>O(n^2)\,</math>
|time=<math>O(n^2)\,</math>
|space=<math>O(1)</math>
|optimal=No
}}

'''कॉकटेल शेकर सॉर्ट''',<ref name="Knuth">{{cite book|title=कंप्यूटर प्रोग्रामिंग की कला|edition=1st|pages=110&ndash;111|last=Knuth|first=Donald E.|author-link=Donald Knuth|volume=3. Sorting and Searching|chapter=Sorting by Exchanging|publisher=[[Addison-Wesley]]|date=1973|isbn=0-201-03803-X}}</ref> इसे द्विदिशात्मक बबल सॉर्ट के रूप में भी जाना जाता है,<ref>{{cite book|first1=Paul E.|last1=Black|first2=Bob|last2=Bockholt|url=http://xlinux.nist.gov/dads/HTML/bidirectionalBubbleSort.html|chapter=bidirectional bubble sort|title=एल्गोरिदम और डेटा संरचनाओं का शब्दकोश|editor1-first=Paul E.|editor1-last=Black|publisher=[[National Institute of Standards and Technology]]|date=24 August 2009|access-date=5 February 2010|archive-url=https://web.archive.org/web/20130316180005/http://xlinux.nist.gov/dads//HTML/bidirectionalBubbleSort.html|archive-date=16 March 2013|url-status=dead}}</ref> कॉकटेल सॉर्ट, शेकर सॉर्ट (जो चयन सॉर्ट के प्रकार को भी संदर्भित कर सकता है), रिपल सॉर्ट, शफ़ल सॉर्ट,<ref name="Duhl1986">{{cite book|first=Martin|last=Duhl|contribution=Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung|title=बबल सॉर्ट एल्गोरिथम के एल्गोरिथम प्रतिनिधित्व से हाइपरकार्ल|language=de|journal=Projektarbeit|year=1986|publisher=Technical University of Kaiserslautern}}</ref> या शटल सॉर्ट, [[ बुलबुले की तरह |बबल सॉर्ट]] का विस्तार है। एल्गोरिदम दो दिशाओं में कार्य करके बबल सॉर्ट का विस्तार करता है। चूँकि यह अधिक बबल सॉर्ट में सुधार करता है, किन्तु यह केवल सामान्य प्रदर्शन सुधार प्रदान करता है।

बबल सॉर्ट के अधिकांश प्रकारों की तरह, कॉकटेल शेकर सॉर्ट का उपयोग मुख्य रूप से शैक्षिक उपकरण के रूप में किया जाता है। [[जल्दी से सुलझाएं|क्विकसॉर्ट]], [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] या टाइमसॉर्ट जैसे अधिक प्रदर्शन करने वाले एल्गोरिदम का उपयोग पायथन और जावा जैसी लोकप्रिय प्रोग्रामिंग भाषाओं में निर्मित सॉर्टिंग लाइब्रेरी द्वारा किया जाता है।<ref>{{Cite web|url=https://bugs.openjdk.java.net/browse/JDK-6804124|title=[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System|website=bugs.openjdk.java.net|access-date=2020-01-11}}</ref><ref>{{Cite web|url=https://mail.python.org/pipermail/python-dev/2002-July/026837.html|title=[Python-Dev] Sorting|last=Peters|first=Tim|date=2002-07-20|access-date=2020-01-11}}</ref>
==स्यूडोकोड==
प्रत्येक बार पूरी सूची में सबसे सरल फ़ॉर्म डाला जाता है:<syntaxhighlight lang="abl">
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
</syntaxhighlight>पहला दाहिनी ओर वाला पास सबसे बड़े अवयव को अंत में उसके सही स्थान पर स्थानांतरित कर देगा, और निम्नलिखित बाईं ओर वाला पास सबसे छोटे अवयव को प्रारंभ में उसके सही स्थान पर स्थानांतरित कर देता है। दूसरा पूर्ण पास दूसरे सबसे बड़े और दूसरे सबसे छोटे अवयवो को उनके सही स्थानों पर स्थानांतरित कर देगा, इत्यादि। इस प्रकार ''i'' पास होने के बाद, सूची में पहला ''i'' और अंतिम ''i'' अवयव अपनी सही स्थिति में हैं, और उन्हें जाँचने की आवश्यकता नहीं है। प्रत्येक बार क्रमबद्ध की जाने वाली सूची के भाग को छोटा करके, संचालन की संख्या आधी की जा सकती है (बबल सॉर्ट वैकल्पिक क्रियान्वयन देखें)।

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

<syntaxhighlight lang="matlab">
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
</syntaxhighlight>
==बबल सॉर्ट से अंतर==
कॉकटेल शेकर सॉर्ट, बबल सॉर्ट का थोड़ा सा बदलाव है।<ref name="Knuth"/> इसमें अंतर यह है कि सूची में बार-बार नीचे से ऊपर की ओर जाने के अतिरिक्त, यह बारी-बारी से नीचे से ऊपर और फिर ऊपर से नीचे की ओर निकलती है। यह मानक बबल सॉर्ट की तुलना में थोड़ा उत्तम प्रदर्शन प्राप्त कर सकता है। इसका कारण यह है कि बबल सॉर्ट सूची से केवल दिशा में निकलता है और इसलिए प्रत्येक पुनरावृत्ति में आइटम को केवल कदम पीछे ले जाया जा सकता है।

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

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

==समष्टि==
[[बड़ा ओ अंकन|बिग ओ नोटेशन]] में कॉकटेल शेकर सॉर्ट <math>O(n^2)</math> की समष्टि है सबसे व्यर्थ स्थिति और औसत स्थिति दोनों के लिए, किन्तु यह निकट <math>O(n)</math> हो जाता है यदि सूची को अधिकतर सॉर्टिंग एल्गोरिदम प्रयुक्त करने से पहले ऑर्डर किया गया है। उदाहरण के लिए, यदि प्रत्येक अवयव ऐसी स्थिति में है जो उस स्थिति से अधिकतम k (k ≥ 1) भिन्न है, जहां वह समाप्त होने वाला है, जिससे कॉकटेल शेकर सॉर्ट की समष्टि <math>O(kn).</math> बन जाती है बबल सॉर्ट के समान परिशोधन के साथ, [[कंप्यूटर प्रोग्रामिंग की कला|कंप्यूटर प्रोग्रामिंग आर्ट]] पुस्तक में कॉकटेल शेकर सॉर्ट की भी संक्षेप में चर्चा की गई है। इस प्रकार अंत में, नुथ बबल सॉर्ट और उसके सुधारों के बारे में बताते हैं:
{{quote|किन्तु इनमें से कोई भी परिशोधन सीधे सम्मिलन से उत्तम एल्गोरिदम की ओर नहीं ले जाता है [अर्थात, [[प्रविष्ट सॉर्ट]]]; और हम पहले से ही जानते हैं कि सीधी प्रविष्टि बड़े&nbsp;''N'' के लिए उपयुक्त नहीं है। [...] संक्षेप में, ऐसा लगता है कि बबल सॉर्ट के पास इसकी अनुशंसा करने के लिए कुछ भी नहीं है, अतिरिक्त एक आकर्षक नाम और इस तथ्य के कि यह कुछ रोचक सैद्धांतिक समस्याओं को जन्म देता है।|डी. ई. नुथ<ref name="Knuth"/>
}}

==संदर्भ                                                                                        ==
{{Reflist}}
==स्रोत==
*{{cite journal|first=R.|last=Hartenstein|journal=The Grand Challenge to Reinvent Computing|title=कंप्यूटिंग का एक नया विश्व मॉडल|publisher=CSBC|date=July 2010|place=[[Belo Horizonte]], Brazil|url=http://www.inf.pucminas.br/sbc2010/anais/pdf/semish/st03_02.pdf|access-date=2011-01-14|archive-url=https://web.archive.org/web/20130807043613/http://www.inf.pucminas.br/sbc2010/anais/pdf/semish/st03_02.pdf|archive-date=2013-08-07|url-status=dead}}

==बाहरी संबंध==
{{Wikibooks|Algorithm implementation|Sorting/Cocktail sort|Cocktail sort}}
*[http://www.hermann-gruber.com/lehre/sorting/Shaker/Shaker-en.html Interactive demo of cocktail sort]
*[https://web.archive.org/web/20061008105719/http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms]
*{{cite web |url=http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx |archive-url=https://web.archive.org/web/20120212173240/http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx |title=.NET Implementation of cocktail sort and several other algorithms |archive-date=2012-02-12}}
{{DEFAULTSORT:Cocktail Sort}}

[[Category:CS1]]
[[Category:CS1 Deutsch-language sources (de)]]
[[Category:Created On 10/07/2023|Cocktail Sort]]
[[Category:Machine Translated Page|Cocktail Sort]]
[[Category:Pages with script errors|Cocktail Sort]]
[[Category:Templates Vigyan Ready|Cocktail Sort]]
[[Category:छँटाई एल्गोरिदम|Cocktail Sort]]
[[Category:तुलना प्रकार|Cocktail Sort]]
[[Category:स्थिर प्रकार|Cocktail Sort]]
[[Category:स्यूडोकोड उदाहरण सहित लेख|Cocktail Sort]]