बबल सोर्ट: Difference between revisions

बबल सोर्ट
	Static visualization of bubble sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance	comparisons, swaps
Best-case performance	comparisons, swaps
Average performance	comparisons, swaps
Worst-case space complexity	total, auxiliary

Revision as of 18:35, 28 March 2023

बबल सॉर्ट, एक सरल जिसे कभी-कभी सिंकिंग सॉर्ट के रूप में संदर्भित किया जाता है, एक सरल सॉर्टिंग एल्गोरिथ्म है जो बार-बार इनपुट सूची तत्व के माध्यम से तत्व द्वारा कदम उठाता है, वर्तमान तत्व की तुलना उसके बाद वाले के साथ करता है, स्वैप (कंप्यूटर विज्ञान) यदि आवश्यक हो तो उनके मूल्य। सूची के माध्यम से ये पास दोहराए जाते हैं जब तक कि पास के दौरान कोई स्वैप नहीं किया जाना चाहिए, जिसका अर्थ है कि सूची पूरी तरह से क्रमबद्ध हो गई है। एल्गोरिथ्म, जो एक तुलना प्रकार है, का नाम सूची के शीर्ष पर बड़े तत्वों के बुलबुले के तरीके के लिए रखा गया है।

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

विश्लेषण

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

प्रदर्शन

बबल सॉर्ट में सबसे खराब स्थिति और औसत जटिलता $O(n^{2})$ होती है , जहां $n$ क्रमित की जा रही वस्तुओं की संख्या है। अधिकांश व्यावहारिक सॉर्टिंग एल्गोरिदम में अक्सर सबसे खराब स्थिति या औसत जटिलता होती है $O(n\log n)$ . दूसरे बबल सॉर्ट से भी तेज चलने वाले अन्य $O(n^{2})$ सॉर्टिंग एल्गोरिदम, जैसे इन्सर्शन सॉर्ट, आमतौर पर बबल सॉर्ट की तुलना में तेज़ी से चलते हैं, और अधिक जटिल नहीं होते हैं। इस कारण से, बबल सॉर्ट वास्तव में अधिकतर मामलों में उपयोग नहीं किया जाता है।

इंसर्शन सॉर्ट की तरह, बबल सॉर्ट अनुकूली सॉर्टिंग है, जो इसे क्विकसॉर्ट जैसे एल्गोरिदम पर लाभ देता है। इसका मतलब यह है कि यह उन एल्गोरिदम से उन्नत प्रदर्शन कर सकता है, जहां सूची पहले से ही अधिकतर क्रमबद्ध होती है (कम संख्या में उलटा (असतत गणित) होने के बावजूद), इस तथ्य के बावजूद कि इसकी औसत-केस टाइम जटिलता खराब है। उदाहरण के लिए, बबल सॉर्ट है एक सूची पर $O(n)$ का समय लेता है जो पहले से ही सॉर्ट हो गई है, जबकि क्विकसॉर्ट अपनी पूरी $O(n\log n)$ क्रमवारी क्रिया को अभी भी पूरा करेगा।

किसी भी सॉर्टिंग एल्गोरिथ्म को सॉर्टेड सूची पर $O(n)$ बनाया जा सकता है, बस एल्गोरिथ्म शुरू होने से पहले सूची की जाँच करने की जरूरत होती है, लेकिन लगभग सॉर्टेड सूचियों पर बेहतर प्रदर्शन को दोहराना मुश्किल होता है।

खरगोश और कछुए

सॉर्ट के दौरान तत्वों को जाना जाना चाहिए और उनके दिशा-निर्देशों का निर्धारण किया जाना चाहिए, क्योंकि तत्व भिन्न गति और दिशाओं में आगे बढ़ते हैं। सूची का तत्व जो सूची के अंत की ओर बढ़ना होता है, वह तेजी से चल सकता है क्योंकि यह लगातार स्वैप में भाग ले सकता है। उदाहरण के लिए, सूची में सबसे बड़ा तत्व हर स्वैप में जीत जाएगा, इसलिए यह पहले ही पास में अपने सॉर्टेड स्थान पर चला जाएगा, चाहे वह शुरुआत के पास से ही क्यों न हो। दूसरी ओर, जब किसी तत्व को सूची के शुरुआत की ओर ले जाना होता है, तो वह पास के अनुसार एक कदम ही दूर जाने के अलावा तेजी से नहीं चल सकता है, इसलिए तत्व धीमी गति से शुरुआत की ओर बढ़ते हैं। अगर सबसे छोटा तत्व सूची के अंत में होता है, तो उसे शुरुआत में लाने के लिए $n-1$ पास की आवश्यकता होगी। इससे इन तत्वों को खरगोश और कछुए के नाम से जाना जाता है, उन चरित्रों के नाम पर जो एसोप की कहानी कछुआ और खरगोश पास की आवश्यकता होगी। इससे इन तत्वों को खरगोश और कछुए के नाम से जाना जाता है, उन चरित्रों के नाम पर जो एसोप की कहानी

बबल सॉर्ट की स्पीड को बढ़ाने के लिए विभिन्न प्रयास किए गए हैं। कॉकटेल किस्म एक दो-दिशीय बबल सॉर्ट है जो शुरुआत से अंत तक जाता है, और फिर उलटी दिशा में जाकर अंत से शुरुआत तक जाता है। यह टर्टल्स को काफी अच्छी तरह से हटा सकता है, लेकिन इसका अधिकतम समय-अवधि $O(n^{2})$ है। कॉम्ब सॉर्ट बड़ी अंतराल से अलग-अलग तत्वों की तुलना करता है, और तुर्तियों को बहुत तेजी से हटा सकता है और फिर लिस्ट को संशोधित करने के लिए स्मूद गैप को छोटा करता है। इसकी औसत गति त्वरित एल्गोरिथम जैसे क्विकसॉर्ट से तुलनायोग्य है।

चरण-दर-चरण उदाहरण

संख्याओं की एक सरणी 5 1 4 2 8 लें, और बबल सॉर्ट का उपयोग करके सरणी को सबसे कम संख्या से सबसे बड़ी संख्या में क्रमबद्ध करें। प्रत्येक चरण में मोटे अक्षरों में लिखे तत्वों की तुलना की जा रही है। तीन पास की आवश्यकता होगी;

पहला पास: ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), यहां, एल्गोरिदम पहले दो तत्वों की तुलना करता है, और 5> 1 के बाद से स्वैप करता है।; ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 से स्वैप करें; ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 से स्वैप करें; ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), अब, चूंकि ये तत्व पहले से ही क्रम में हैं (8 > 5), एल्गोरिदम उन्हें स्वैप नहीं करता है।
दूसरा पास: ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ); ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 से स्वैप करें; ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

अब, सरणी पहले से ही क्रमबद्ध है, लेकिन एल्गोरिथ्म को पता नहीं है कि यह पूरा हो गया है या नहीं। एल्गोरिदम को बिना किसी स्वैप के एक अतिरिक्त संपूर्ण पास की आवश्यकता होती है ताकि यह पता चल सके कि यह सॉर्ट किया गया है।

तीसरा दर्रा: ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

कार्यान्वयन

स्यूडोकोड कार्यान्वयन

स्यूडोकोड में एल्गोरिथ्म को (0-आधारित सरणी) के रूप में व्यक्त किया जा सकता है:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            { if this pair is out of order }
            if A[i-1] > A[i] then
                { swap them and remember something changed }
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

बबल सॉर्ट का अनुकूलन

बबल सॉर्ट एल्गोरिथ्म को यह देखते हुए अनुकूलित किया जा सकता है कि n-वें पास n-वें सबसे बड़े तत्व को ढूंढता है और इसे अपने अंतिम स्थान पर रखता है। इसलिए, n-वें समय के लिए चलते समय आंतरिक लूप अंतिम n-1 आइटम को देखने से बच सकता है:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

अधिक आम तौर पर, ऐसा हो सकता है कि एक पास पर एक से अधिक तत्व अपनी अंतिम स्थिति में रखे जाते हैं। विशेष रूप से, प्रत्येक पास के बाद, अंतिम स्वैप के बाद सभी तत्वों को क्रमबद्ध किया जाता है, और फिर से जाँच करने की आवश्यकता नहीं होती है। यह कई तत्वों को छोड़ने की अनुमति देता है, जिसके परिणामस्वरूप तुलनात्मक गणना में लगभग 50% सुधार होता है (हालांकि स्वैप गणना में कोई सुधार नहीं होता है), और बहुत कम जटिलता जोड़ता है क्योंकि नया कोड स्वैप किए गए चर को कम करता है:

स्यूडोकोड में इसे पूरा करने के लिए, निम्नलिखित लिखा जा सकता है:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        newn := 0
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                newn := i
            end if
        end for
        n := newn
    until n ≤ 1
end procedure

वैकल्पिक संशोधन, जैसे कि कॉकटेल शेकर प्रकार बार-बार तुलना करने और आसन्न वस्तुओं की अदला-बदली के समान विचार रखते हुए बबल सॉर्ट प्रदर्शन में सुधार करने का प्रयास करते हैं।

प्रयोग करें

बुलबुले की तरह। सूची को कार्टेसियन समन्वय प्रणाली में प्लॉट किया गया था, जिसमें प्रत्येक बिंदु (x, y) इंगित करता है कि मान y इंडेक्स x पर संग्रहीत है। फिर सूची को प्रत्येक पिक्सेल के मान के अनुसार बबल सॉर्ट द्वारा क्रमबद्ध किया जाएगा। ध्यान दें कि सबसे बड़ा अंत पहले क्रमबद्ध हो जाता है, छोटे तत्वों को उनकी सही स्थिति में जाने में अधिक समय लगता है।

हालाँकि बबल सॉर्ट समझने और लागू करने के लिए सबसे सरल सॉर्टिंग एल्गोरिदम में से एक है, लेकिन इसका बिग ओ नोटेशन|O(n²) जटिलता का अर्थ है कि तत्वों की एक छोटी संख्या से अधिक की सूचियों पर इसकी दक्षता नाटकीय रूप से घट जाती है। यहां तक कि सरल O(n²) सॉर्टिंग एल्गोरिदम, इंसर्शन सॉर्ट जैसे एल्गोरिदम आमतौर पर काफी अधिक कुशल होते हैं।

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

शब्दजाल फ़ाइल, जो प्रसिद्ध रूप से bogosort को आर्किटेपिकल [एसआईसी] विकृत रूप से भयानक एल्गोरिथ्म कहती है, बबल सॉर्ट को जेनेरिक बैड एल्गोरिथम भी कहती है।^[5] कंप्यूटर प्रोग्रामिंग की कला में डोनाल्ड नुथ ने निष्कर्ष निकाला कि बबल सॉर्ट में इसकी सिफारिश करने के लिए कुछ भी नहीं है, सिवाय एक आकर्षक नाम के और तथ्य यह है कि यह कुछ दिलचस्प सैद्धांतिक समस्याओं की ओर जाता है, जिनमें से कुछ पर वह फिर चर्चा करता है।^[6] बबल सॉर्ट बिग ओ नोटेशन है जो सबसे खराब स्थिति में इंसर्शन सॉर्ट करने के लिए रनिंग टाइम के बराबर है, लेकिन आवश्यक स्वैप की संख्या में दो एल्गोरिदम बहुत भिन्न होते हैं। एस्ट्राचन जैसे प्रायोगिक परिणाम भी दिखाते हैं कि सम्मिलन क्रम यादृच्छिक सूचियों पर भी काफी बेहतर प्रदर्शन करता है। इन कारणों से कई आधुनिक एल्गोरिदम पाठ्यपुस्तक सम्मिलन प्रकार के पक्ष में बबल सॉर्ट एल्गोरिदम का उपयोग करने से बचते हैं।

बबल सॉर्ट भी आधुनिक सीपीयू हार्डवेयर के साथ खराब तरीके से इंटरैक्ट करता है। यह सम्मिलन क्रम के रूप में कम से कम दो बार लिखता है, दो बार कई कैश मिस करता है, और असीमित रूप से अधिक शाखा भविष्यवाणी करता है।^{[citation needed]} जावा (प्रोग्रामिंग भाषा) में एस्ट्राचन सॉर्टिंग स्ट्रिंग्स द्वारा किए गए प्रयोग बबल सॉर्ट को एक चयन छांटना के रूप में लगभग एक-पांचवें और चयन सॉर्ट के रूप में 70% तेज़ दिखाते हैं।^[4] कंप्यूटर ग्राफ़िक्स में बबल सॉर्ट लगभग-सॉर्ट किए गए सरणियों में एक बहुत छोटी त्रुटि (जैसे केवल दो तत्वों की अदला-बदली) का पता लगाने और इसे केवल रैखिक जटिलता (2n) के साथ ठीक करने की क्षमता के लिए लोकप्रिय है। उदाहरण के लिए, इसका उपयोग बहुभुज भरने वाले एल्गोरिदम में किया जाता है, जहां बाउंडिंग लाइनों को उनके एक्स समन्वय द्वारा एक विशिष्ट स्कैन लाइन (एक्स अक्ष के समानांतर एक रेखा) पर क्रमबद्ध किया जाता है और y को बढ़ाने के साथ उनके क्रम में परिवर्तन होता है (दो तत्वों की अदला-बदली होती है) दो पंक्तियों का चौराहा। बबल सॉर्ट एक स्थिर सॉर्ट एल्गोरिथम है, जैसे सम्मिलन सॉर्ट।

विविधताएं

ऑड-ईवन सॉर्ट, मैसेज पासिंग सिस्टम के लिए बबल सॉर्ट का समानांतर संस्करण है।
पास बाएं से दाएं के बजाय दाएं से बाएं हो सकते हैं। यह अंत में जोड़े गए अनसोर्टेड आइटम वाली सूचियों के लिए अधिक कुशल है।
कॉकटेल शेकर सॉर्ट बारी-बारी से बायीं ओर और दायीं ओर गुजरता है।
मैं विश्वास नहीं कर सकता कि यह सॉर्ट कर सकता है एक सॉर्टिंग एल्गोरिदम है जो बबल सॉर्ट का गलत संस्करण प्रतीत होता है, लेकिन औपचारिक रूप से सम्मिलन प्रकार के समान काम करने के लिए सिद्ध किया जा सकता है।^[7]

नाम पर बहस

बबल सॉर्ट को कभी-कभी डूबने वाली सॉर्ट के रूप में संदर्भित किया जाता है।^[8] उदाहरण के लिए, डोनाल्ड नुथ मूल्यों को उनके वांछित स्थान पर या उनके सम्मिलन के रूप में वर्णित करता है, जिससे [मूल्य] अपने उचित स्तर पर व्यवस्थित हो जाता है, और सॉर्टिंग की इस विधि को कभी-कभी सिफ्टिंग या सिंकिंग तकनीक कहा जाता है।^[9] यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग लेकिन समान रूप से मान्य दृष्टिकोणों से मान सकता है:

बड़े मूल्यों को भारी माना जा सकता है और इसलिए सूची के निचले भाग में उत्तरोत्तर डूबते देखा जा सकता है
छोटे मूल्यों को हल्का माना जा सकता है और इसलिए उन्हें सूची के शीर्ष पर उत्तरोत्तर बुलबुले के रूप में देखा जा सकता है।

↑ Cortesi, Aldo (27 April 2007). "Visualising Sorting Algorithms". Retrieved 16 March 2017.
↑ "[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System". bugs.openjdk.java.net. Retrieved 2020-01-11.
↑ Peters, Tim (2002-07-20). "[Python-Dev] Sorting". Retrieved 2020-01-11.
↑ ^4.0 ^4.1 Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5. doi:10.1145/792548.611918. ISSN 0097-8418.
↑ "jargon, node: bogo-sort".
↑ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging. "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)
↑ Fung, Stanley P. Y. (3 October 2021). "Is this the simplest (and most surprising) sorting algorithm ever?". arXiv:2110.01111.
↑ Black, Paul E. (24 August 2009). "बुलबुले की तरह". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 1 October 2014.
↑ Knuth, Donald (1997). The Art of Computer Programming: Volume 3: Searching and Sorting. p. 80. ISBN 0201896850.
↑ Lai Stirland, Sarah (2007-11-14). "ओबामा ने पास किया अपना गूगल इंटरव्यू". Wired. Retrieved 2020-10-27.
↑ Barack Obama, Eric Schmidt (Nov 14, 2007). Barack Obama | Candidates at Google (Video) (YouTube) (in English). Mountain View, CA 94043 The Googleplex: Talks at Google. Event occurs at 23:20. Archived from the original on September 7, 2019. Retrieved Sep 18, 2019.{{cite AV media}}: CS1 maint: location (link)

संदर्भ

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.40.
Sorting in the Presence of Branch Prediction and Caches
Fundamentals of Data Structures by Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed ISBN 81-7371-605-6
Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis
Computer Integrated Manufacturing by Spasic PhD, Srdic MSc, Open Source, 1987.[1]

बाहरी संबंध

Martin, David R. (2007). "Animated Sorting Algorithms: Bubble Sort". Archived from the original on 2015-03-03. – graphical demonstration
"Lafore's Bubble Sort". (Java applet animation)
OEIS sequence A008302 (Table (statistics) of the number of permutations of [n] that need k pair-swaps during the sorting)

[1] Cortesi, Aldo (27 April 2007). "Visualising Sorting Algorithms". Retrieved 16 March 2017.

[2] "[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System". bugs.openjdk.java.net. Retrieved 2020-01-11.

[3] Peters, Tim (2002-07-20). "[Python-Dev] Sorting". Retrieved 2020-01-11.

[Astrachan2003-4] 4.0 ^4.1 Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5. doi:10.1145/792548.611918. ISSN 0097-8418.

[5] "jargon, node: bogo-sort".

[Knuth-6] Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging. "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)

[7] Fung, Stanley P. Y. (3 October 2021). "Is this the simplest (and most surprising) sorting algorithm ever?". arXiv:2110.01111.

[8] Black, Paul E. (24 August 2009). "बुलबुले की तरह". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 1 October 2014.

[9] Knuth, Donald (1997). The Art of Computer Programming: Volume 3: Searching and Sorting. p. 80. ISBN 0201896850.

[10] Lai Stirland, Sarah (2007-11-14). "ओबामा ने पास किया अपना गूगल इंटरव्यू". Wired. Retrieved 2020-10-27.

[11] Barack Obama, Eric Schmidt (Nov 14, 2007). Barack Obama | Candidates at Google (Video) (YouTube) (in English). Mountain View, CA 94043 The Googleplex: Talks at Google. Event occurs at 23:20. Archived from the original on September 7, 2019. Retrieved Sep 18, 2019.{{cite AV media}}: CS1 maint: location (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{Short description|Simple comparison sorting algorithm}}
-{{refimprove|date=November 2016}}
 {{Infobox Algorithm
 |name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
@@ Line 12: / Line 11: @@
 |optimal=No
 }}
-बबल सॉर्ट, जिसे कभी-कभी सिंकिंग सॉर्ट के रूप में संदर्भित किया जाता है, एक सरल [[छँटाई एल्गोरिथ्म]] है जो बार-बार इनपुट सूची तत्व के माध्यम से तत्व द्वारा कदम उठाता है, वर्तमान तत्व की तुलना उसके बाद वाले के साथ करता है, [[स्वैप (कंप्यूटर विज्ञान)]] यदि आवश्यक हो तो उनके मूल्य। सूची के माध्यम से ये पास दोहराए जाते हैं जब तक कि पास के दौरान कोई स्वैप नहीं किया जाना चाहिए, जिसका अर्थ है कि सूची पूरी तरह से क्रमबद्ध हो गई है। एल्गोरिथ्म, जो एक तुलना प्रकार है, का नाम सूची के शीर्ष पर बड़े तत्वों के बुलबुले के तरीके के लिए रखा गया है।
+बबल सॉर्ट, एक सरल जिसे कभी-कभी सिंकिंग सॉर्ट के रूप में संदर्भित किया जाता है, एक सरल [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिथ्म]] है जो बार-बार इनपुट सूची तत्व के माध्यम से तत्व द्वारा कदम उठाता है, वर्तमान तत्व की तुलना उसके बाद वाले के साथ करता है, [[स्वैप (कंप्यूटर विज्ञान)]] यदि आवश्यक हो तो उनके मूल्य। सूची के माध्यम से ये पास दोहराए जाते हैं जब तक कि पास के दौरान कोई स्वैप नहीं किया जाना चाहिए, जिसका अर्थ है कि सूची पूरी तरह से क्रमबद्ध हो गई है। एल्गोरिथ्म, जो एक तुलना प्रकार है, का नाम सूची के शीर्ष पर बड़े तत्वों के बुलबुले के तरीके के लिए रखा गया है।
-यह सरल एल्गोरिदम वास्तविक दुनिया के उपयोग में खराब प्रदर्शन करता है और प्राथमिक रूप से एक शैक्षिक उपकरण के रूप में उपयोग किया जाता है। [[जल्दी से सुलझाएं]], टाइमसॉर्ट या [[ मर्ज़ सॉर्ट ]] जैसे अधिक कुशल एल्गोरिदम का उपयोग पायथन और जावा जैसी लोकप्रिय प्रोग्रामिंग भाषाओं में निर्मित सॉर्टिंग लाइब्रेरी द्वारा किया जाता है।<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> <!-- sorted scan line display list stepped to next line is usually nearly sorted.
+यह सरल एल्गोरिदम वास्तविक दुनिया के उपयोग में खराब प्रदर्शन करता है और प्राथमिक रूप से एक शैक्षिक उपकरण के रूप में उपयोग किया जाता है। [[जल्दी से सुलझाएं|क्विकसॉर्ट]], टाइमसॉर्ट या [[ मर्ज़ सॉर्ट ]] जैसे अधिक कुशल एल्गोरिदम का उपयोग पाइथन और जावा जैसी लोकप्रिय प्रोग्रामिंग भाषाओं में निर्मित सॉर्टिंग लाइब्रेरी द्वारा किया जाता है।<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>
-Bubble sort may be been found as early as 1956; then referred to as "sorting by exchange"<ref name="Astrachan">{{cite web |last1=Astrachan |first1=Owen |title=Bubble Sort: An Archaeological Algorithmic Analysis |url=https://users.cs.duke.edu/~ola/bubble/bubble.html |access-date=8 February 2019}}</ref> -->
 == विश्लेषण ==
-[[File:Bubble-sort-example-300px.gif|300px|thumb|right|बुलबुला छँटाई का एक उदाहरण। सूची की शुरुआत से शुरू करते हुए, प्रत्येक आसन्न जोड़ी की तुलना करें, उनकी स्थिति स्वैप करें यदि वे सही क्रम में नहीं हैं (बाद वाला पहले वाले से छोटा है)। प्रत्येक पुनरावृत्ति के बाद, एक कम तत्व (अंतिम वाला) की तुलना करने की आवश्यकता होती है जब तक कि तुलना करने के लिए कोई और तत्व शेष न हो।]]
+[[File:Bubble-sort-example-300px.gif|300px|thumb|right|बबल सॉर्ट का एक उदाहरण। सूची की शुरुआत से शुरू करके, प्रत्येक आसपास के जोड़े की तुलना करें, अगर वे सही क्रम में नहीं हैं (दूसरा तत्व पहले वाले से छोटा है) तो उनकी स्थिति को बदलें। प्रत्येक इटरेशन के बाद, तुलना की जाने वाली एक कम तत्व (अंतिम तत्व) होती है जब तक तुलना करने के लिए कोई तत्व नहीं बचता है।]]
 === प्रदर्शन ===
-बबल सॉर्ट में सबसे खराब स्थिति और औसत जटिलता होती है <math>O(n^2)</math>, कहाँ <math>n</math> क्रमित की जा रही वस्तुओं की संख्या है। अधिकांश व्यावहारिक छँटाई एल्गोरिदम में अक्सर सबसे खराब स्थिति या औसत जटिलता होती है <math>O(n\log n)</math>. अन्य भी <math>O(n^2)</math> सॉर्टिंग एल्गोरिदम, जैसे [[सम्मिलन सॉर्ट]], आमतौर पर बबल सॉर्ट की तुलना में तेज़ी से चलते हैं, और अधिक जटिल नहीं होते हैं। इस कारण से, व्यवहार में बबल सॉर्ट का उपयोग शायद ही कभी किया जाता है।
+बबल सॉर्ट में सबसे खराब स्थिति और औसत जटिलता <math>O(n^2)</math>होती है , जहां <math>n</math> क्रमित की जा रही वस्तुओं की संख्या है। अधिकांश व्यावहारिक सॉर्टिंग एल्गोरिदम में अक्सर सबसे खराब स्थिति या औसत जटिलता होती है <math>O(n\log n)</math>. दूसरे बबल सॉर्ट से भी तेज चलने वाले अन्य <math>O(n^2)</math> सॉर्टिंग एल्गोरिदम, जैसे [[सम्मिलन सॉर्ट|इन्सर्शन सॉर्ट]], आमतौर पर बबल सॉर्ट की तुलना में तेज़ी से चलते हैं, और अधिक जटिल नहीं होते हैं। इस कारण से, बबल सॉर्ट वास्तव में अधिकतर मामलों में उपयोग नहीं किया जाता है।
-इंसर्शन सॉर्ट की तरह, बबल सॉर्ट [[ अनुकूली छँटाई ]] है, जो इसे क्विकॉर्ट जैसे एल्गोरिदम पर लाभ देता है। इसका मतलब यह है कि यह उन एल्गोरिदम से बेहतर प्रदर्शन कर सकता है, जहां सूची पहले से ही ज्यादातर क्रमबद्ध है (कम संख्या में [[उलटा (असतत गणित)]] होने के बावजूद), इस तथ्य के बावजूद कि इसकी औसत-केस टाइम जटिलता खराब है। उदाहरण के लिए, बबल सॉर्ट है <math>O(n)</math> एक सूची पर जो पहले से ही क्रमबद्ध है, जबकि क्विकॉर्ट अभी भी अपना पूरा प्रदर्शन करेगा <math>O(n \log n)</math> छँटाई प्रक्रिया।
+इंसर्शन सॉर्ट की तरह, बबल सॉर्ट [[ अनुकूली छँटाई | अनुकूली सॉर्टिंग]] है, जो इसे क्विकसॉर्ट जैसे एल्गोरिदम पर लाभ देता है। इसका मतलब यह है कि यह उन एल्गोरिदम से उन्नत प्रदर्शन कर सकता है, जहां सूची पहले से ही अधिकतर क्रमबद्ध होती है (कम संख्या में [[उलटा (असतत गणित)]] होने के बावजूद), इस तथ्य के बावजूद कि इसकी औसत-केस टाइम जटिलता खराब है। उदाहरण के लिए, बबल सॉर्ट है  एक सूची पर <math>O(n)</math> का समय लेता है जो पहले से ही सॉर्ट हो गई है, जबकि क्विकसॉर्ट अपनी पूरी <math>O(n \log n)</math> क्रमवारी क्रिया को अभी भी पूरा करेगा।
-जबकि कोई भी छँटाई एल्गोरिथ्म बनाया जा सकता है <math>O(n)</math> एल्गोरिथम के चलने से पहले केवल सूची की जाँच करके पूर्वनिर्धारित सूची पर, लगभग क्रमबद्ध सूचियों पर बेहतर प्रदर्शन को दोहराना कठिन होता है।
+किसी भी सॉर्टिंग एल्गोरिथ्म को सॉर्टेड सूची पर <math>O(n)</math> बनाया जा सकता है, बस एल्गोरिथ्म शुरू होने से पहले सूची की जाँच करने की जरूरत होती है, लेकिन लगभग सॉर्टेड सूचियों पर बेहतर प्रदर्शन को दोहराना मुश्किल होता है।
 ===खरगोश और कछुए ===
-सॉर्ट के दौरान तत्वों को जिस दूरी और दिशा में जाना चाहिए, वह बबल सॉर्ट के प्रदर्शन को निर्धारित करता है क्योंकि तत्व अलग-अलग दिशाओं में अलग-अलग गति से चलते हैं। एक तत्व जिसे सूची के अंत की ओर जाना चाहिए वह जल्दी से आगे बढ़ सकता है क्योंकि यह लगातार स्वैप में भाग ले सकता है। उदाहरण के लिए, सूची में सबसे बड़ा तत्व प्रत्येक स्वैप जीतेगा, इसलिए यह शुरुआत के निकट शुरू होने पर भी पहले पास पर अपनी क्रमबद्ध स्थिति में चला जाता है। दूसरी ओर, एक तत्व जिसे सूची की शुरुआत की ओर बढ़ना चाहिए, वह एक चरण प्रति चरण से अधिक तेजी से नहीं बढ़ सकता है, इसलिए तत्व बहुत धीमी गति से शुरुआत की ओर बढ़ते हैं। यदि सूची के अंत में सबसे छोटा तत्व है, तो यह लगेगा <math>n -1</math> इसे शुरुआत में ले जाने के लिए पास करता है। इसने इस प्रकार के तत्वों को क्रमशः खरगोश और कछुओं का नाम दिया है, ईसप की [[कछुआ और खरगोश]] की कथा के पात्रों के बाद।
+सॉर्ट के दौरान तत्वों को जाना जाना चाहिए और उनके दिशा-निर्देशों का निर्धारण किया जाना चाहिए, क्योंकि तत्व भिन्न गति और दिशाओं में आगे बढ़ते हैं। सूची का तत्व जो सूची के अंत की ओर बढ़ना होता है, वह तेजी से चल सकता है क्योंकि यह लगातार स्वैप में भाग ले सकता है। उदाहरण के लिए, सूची में सबसे बड़ा तत्व हर स्वैप में जीत जाएगा, इसलिए यह पहले ही पास में अपने सॉर्टेड स्थान पर चला जाएगा, चाहे वह शुरुआत के पास से ही क्यों न हो। दूसरी ओर, जब किसी तत्व को सूची के शुरुआत की ओर ले जाना होता है, तो वह पास के अनुसार एक कदम ही दूर जाने के अलावा तेजी से नहीं चल सकता है, इसलिए तत्व धीमी गति से शुरुआत की ओर बढ़ते हैं। अगर सबसे छोटा तत्व सूची के अंत में होता है, तो उसे शुरुआत में लाने के लिए  <math>n -1</math> पास की आवश्यकता होगी। इससे इन तत्वों को खरगोश और कछुए के नाम से जाना जाता है, उन चरित्रों के नाम पर जो एसोप की कहानी [[कछुआ और खरगोश]] पास की आवश्यकता होगी। इससे इन तत्वों को खरगोश और कछुए के नाम से जाना जाता है, उन चरित्रों के नाम पर जो एसोप की कहानी
-बबल सॉर्ट की गति में सुधार के लिए कछुओं को खत्म करने के लिए कई प्रयास किए गए हैं। [[ कॉकटेल किस्म ]] एक द्वि-दिशात्मक बबल सॉर्ट है जो शुरुआत से अंत तक जाता है, और फिर खुद को उलट देता है, अंत से शुरू होता है। यह कछुओं को काफी अच्छी तरह से हिला सकता है, लेकिन यह बरकरार रहता है <math>O(n^2)</math> सबसे खराब स्थिति जटिलता। कंघी छँटाई बड़े अंतराल से अलग किए गए तत्वों की तुलना करती है, और सूची को सुचारू करने के लिए छोटे और छोटे अंतराल पर आगे बढ़ने से पहले कछुओं को बहुत तेज़ी से स्थानांतरित कर सकती है। इसकी औसत गति क्विकसॉर्ट जैसे तेज एल्गोरिदम के बराबर है।
+बबल सॉर्ट की स्पीड को बढ़ाने के लिए विभिन्न प्रयास किए गए हैं। [[ कॉकटेल किस्म ]] एक दो-दिशीय बबल सॉर्ट है जो शुरुआत से अंत तक जाता है, और फिर उलटी दिशा में जाकर अंत से शुरुआत तक जाता है। यह टर्टल्स को काफी अच्छी तरह से हटा सकता है, लेकिन इसका अधिकतम समय-अवधि  <math>O(n^2)</math> है। कॉम्ब सॉर्ट बड़ी अंतराल से अलग-अलग तत्वों की तुलना करता है, और तुर्तियों को बहुत तेजी से हटा सकता है और फिर लिस्ट को संशोधित करने के लिए स्मूद गैप को छोटा करता है। इसकी औसत गति त्वरित एल्गोरिथम जैसे क्विकसॉर्ट से तुलनायोग्य है।
 === चरण-दर-चरण उदाहरण ===
@@ Line 135: / Line 133: @@
 == नाम पर बहस ==
 बबल सॉर्ट को कभी-कभी डूबने वाली सॉर्ट के रूप में संदर्भित किया जाता है।<ref>{{cite web |url=https://xlinux.nist.gov/dads/HTML/bubblesort.html |title=बुलबुले की तरह|last=Black |first=Paul E. |date=24 August 2009 |work=[[Dictionary of Algorithms and Data Structures]] |publisher=[[National Institute of Standards and Technology]] |access-date=1 October 2014}}</ref>
-उदाहरण के लिए, डोनाल्ड नुथ मूल्यों को उनके वांछित स्थान पर या उनके सम्मिलन के रूप में वर्णित करता है, जिससे [मूल्य] अपने उचित स्तर पर व्यवस्थित हो जाता है, और छँटाई की इस विधि को कभी-कभी सिफ्टिंग या सिंकिंग तकनीक कहा जाता है।<ref>{{cite book|first1=Donald |last1=Knuth |author-link=Donald Knuth |title=The Art of Computer Programming: Volume 3: Searching and Sorting |year=1997 |page=80 |isbn=0201896850}}</ref>
+उदाहरण के लिए, डोनाल्ड नुथ मूल्यों को उनके वांछित स्थान पर या उनके सम्मिलन के रूप में वर्णित करता है, जिससे [मूल्य] अपने उचित स्तर पर व्यवस्थित हो जाता है, और सॉर्टिंग की इस विधि को कभी-कभी सिफ्टिंग या सिंकिंग तकनीक कहा जाता है।<ref>{{cite book|first1=Donald |last1=Knuth |author-link=Donald Knuth |title=The Art of Computer Programming: Volume 3: Searching and Sorting |year=1997 |page=80 |isbn=0201896850}}</ref>
 यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग लेकिन समान रूप से मान्य दृष्टिकोणों से मान सकता है:
 # बड़े मूल्यों को भारी माना जा सकता है और इसलिए सूची के निचले भाग में उत्तरोत्तर डूबते देखा जा सकता है

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

बबल सोर्ट: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:35, 28 March 2023

Contents

विश्लेषण

प्रदर्शन

खरगोश और कछुए

चरण-दर-चरण उदाहरण

कार्यान्वयन

स्यूडोकोड कार्यान्वयन

बबल सॉर्ट का अनुकूलन

प्रयोग करें

विविधताएं

नाम पर बहस

लोकप्रिय संस्कृति में

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Static visualization of bubble sort^[1]
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$ comparisons, $O(n^{2})$ swaps
Best-case performance	$O(n)$ comparisons, $O(1)$ swaps
Average performance	$O(n^{2})$ comparisons, $O(n^{2})$ swaps
Worst-case space complexity	$O(n)$ total, $O(1)$ auxiliary

Anonymous

Search

बबल सोर्ट: Difference between revisions

Revision as of 18:35, 28 March 2023

विश्लेषण

प्रदर्शन

खरगोश और कछुए

चरण-दर-चरण उदाहरण

कार्यान्वयन

स्यूडोकोड कार्यान्वयन

बबल सॉर्ट का अनुकूलन

प्रयोग करें

विविधताएं

नाम पर बहस

लोकप्रिय संस्कृति में

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories