कॉकटेल शेकर सॉर्ट: Difference between revisions

From Vigyanwiki
(Created page with "{{Infobox Algorithm |class=Sorting algorithm |image=Visualization of shaker sort |data=Array |best-time= <ma...")
 
No edit summary
Line 10: Line 10:
}}
}}


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




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


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


<syntaxhighlight lang="matlab">
<syntaxhighlight lang="matlab">
Line 77: Line 77:


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


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


एक और अनुकूलन यह हो सकता है कि एल्गोरिदम याद रखे कि अंतिम वास्तविक स्वैप कहां किया गया है। अगले पुनरावृत्ति में, इस सीमा से अधिक कोई स्वैप नहीं होगा और एल्गोरिदम में छोटे पास होंगे। चूंकि कॉकटेल शेकर सॉर्ट द्विदिश रूप से होता है, संभावित स्वैप की सीमा, जो कि परीक्षण की जाने वाली सीमा है, प्रति पास कम हो जाएगी, इस प्रकार कुल चलने का समय थोड़ा कम हो जाएगा।
एक और अनुकूलन यह हो सकता है कि एल्गोरिदम याद रखे कि अंतिम वास्तविक स्वैप कहां किया गया है। अगले पुनरावृत्ति में, इस सीमा से अधिक कोई स्वैप नहीं होगा और एल्गोरिदम में छोटे पास होंगे। चूंकि कॉकटेल शेकर सॉर्ट द्विदिश रूप से होता है, संभावित स्वैप की सीमा, जो कि परीक्षण की जाने वाली सीमा है, प्रति पास कम हो जाएगी, इस प्रकार कुल चलने का समय थोड़ा कम हो जाएगा।
Line 101: Line 101:
*[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]
*[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}}
*{{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}}
{{sorting}}
{{DEFAULTSORT:Cocktail Sort}}
{{DEFAULTSORT:Cocktail Sort}}
[[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: तुलना प्रकार]] [[Category: छँटाई एल्गोरिदम]] [[Category: स्थिर प्रकार]]  
[[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: तुलना प्रकार]] [[Category: छँटाई एल्गोरिदम]] [[Category: स्थिर प्रकार]]  

Revision as of 11:20, 18 July 2023

कॉकटेल शेकर सॉर्ट
Visualization of shaker sort
ClassSorting algorithm
Data structureArray
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity

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

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


छद्मकोड

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

प्रक्रिया कॉकटेलशेकरसॉर्ट(ए: क्रमबद्ध वस्तुओं की सूची) है
    करना
        अदला-बदली:=झूठा
        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


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

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

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

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

जटिलता

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

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[1]

संदर्भ

  1. 1.0 1.1 1.2 Knuth, Donald E. (1973). "Sorting by Exchanging". कंप्यूटर प्रोग्रामिंग की कला. Vol. 3. Sorting and Searching (1st ed.). Addison-Wesley. pp. 110–111. ISBN 0-201-03803-X.
  2. Black, Paul E.; Bockholt, Bob (24 August 2009). "bidirectional bubble sort". In Black, Paul E. (ed.). एल्गोरिदम और डेटा संरचनाओं का शब्दकोश. National Institute of Standards and Technology. Archived from the original on 16 March 2013. Retrieved 5 February 2010.
  3. Duhl, Martin (1986). "Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung". बबल सॉर्ट एल्गोरिथम के एल्गोरिथम प्रतिनिधित्व से हाइपरकार्ल. {{cite book}}: |journal= ignored (help)
  4. "[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System". bugs.openjdk.java.net. Retrieved 2020-01-11.
  5. Peters, Tim (2002-07-20). "[Python-Dev] Sorting". Retrieved 2020-01-11.


स्रोत

बाहरी संबंध