बबल सोर्ट: 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 19:27, 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 ), यहाँ, एल्गोरिथ्म पहले दो तत्वों की समानता करता है और तबदीली करता है क्योंकि 1, 5 से छोटा है।; ( 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-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]

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

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

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

कंप्यूटर ग्राफिक्स में, बबल सॉर्ट बहुत छोटी त्रुटियों को भी पकड़ने की क्षमता के लिए लोकप्रिय है (जैसे कि बस दो तत्वों की एक विन्यास विफलता). उदाहरण के लिए, यह एक बहुभुज भरने वाले एल्गोरिदम में उपयोग किया जाता है, जहां बाउंडिंग लाइनें एक विशेष स्कैन लाइन (एक्स-अक्ष के पार) पर उनकी एक्स-अक्ष की अनुक्रमणिका के अनुसार क्रमबद्ध की जाती हैं, और उनकी 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 11: / 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>
@@ Line 18: / Line 18: @@
 == विश्लेषण ==
-[[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> है। कॉम्ब सॉर्ट बड़ी अंतराल से अलग-अलग तत्वों की समानता करता है, और तुर्तियों को बहुत तेजी से हटा सकता है और फिर लिस्ट को संशोधित करने के लिए स्मूद गैप को छोटा करता है। इसकी औसत गति त्वरित एल्गोरिथम जैसे क्विकसॉर्ट से समानतायोग्य है।
 === चरण-दर-चरण उदाहरण ===
-संख्याओं की एक सरणी "5 1 4 2 8" को लोअपन से सबसे छोटी संख्या से बड़ी संख्या तक क्रमबद्ध करें। प्रत्येक स्टेप में, बोल्ड में लिखी गई तत्वों की तुलना की जाती है। तीन पास की आवश्यकता होगी।
+संख्याओं की एक सरणी "5 1 4 2 8" को लोअपन से सबसे छोटी संख्या से बड़ी संख्या तक क्रमबद्ध करें। प्रत्येक स्टेप में, बोल्ड में लिखी गई तत्वों की समानता की जाती है। तीन पास की आवश्यकता होगी।
 ;पहला पास
-:( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), यहाँ, एल्गोरिथ्म पहले दो तत्वों की तुलना करता है और तबदीली करता है क्योंकि 1, 5 से छोटा है।
+:( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), यहाँ, एल्गोरिथ्म पहले दो तत्वों की समानता करता है और तबदीली करता है क्योंकि 1, 5 से छोटा है।
 :( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 से स्वैप करें
 :( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 से स्वैप करें
@@ Line 45: / Line 45: @@
 :( 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 )
@@ Line 93: / Line 93: @@
 end procedure
 </syntaxhighlight>
-और सामान्यतः, एक ही पास में एक से अधिक तत्व अपनी अंतिम स्थान पर रखे जाने की स्थिति हो सकती है। विशेष रूप से, प्रत्येक पास के बाद, अंतिम स्वैप के बाद सभी तत्व सॉर्ट हो जाते हैं और फिर से जाँच करने की आवश्यकता नहीं होती है। इससे कई तत्वों को छोड़ा जा सकता है, तुलना गिनती में अधिकतर 50% की बेहतरी होती है (चूंकि स्वैप की गिनती में कोई सुधार नहीं होता है), और इससे बहुत ही कम पेशेवरता जुड़ती है क्योंकि नई कोड "विनिमयित" चर सम्मलित करता है
+और सामान्यतः, एक ही पास में एक से अधिक तत्व अपनी अंतिम स्थान पर रखे जाने की स्थिति हो सकती है। विशेष रूप से, प्रत्येक पास के बाद, अंतिम स्वैप के बाद सभी तत्व सॉर्ट हो जाते हैं और फिर से जाँच करने की आवश्यकता नहीं होती है। इससे कई तत्वों को छोड़ा जा सकता है, समानता गिनती में अधिकतर 50% की बेहतरी होती है (चूंकि स्वैप की गिनती में कोई सुधार नहीं होता है), और इससे बहुत ही कम पेशेवरता जुड़ती है क्योंकि नई कोड "विनिमयित" चर सम्मलित करता है
 स्यूडोकोड में, निम्नलिखित लिखा जा सकता है
@@ Line 111: / Line 111: @@
 end procedure
 </syntaxhighlight>
-वैकल्पिक संशोधन, जैसे कि [[ कॉकटेल शेकर प्रकार ]] बबल सॉर्ट के प्रदर्शन में सुधार करने की कोशिश करते हैं चूँकि आसपास के आइटमों की तुलना और तबादला करने के विचार को एक साथ रखने का विचार बनाए रखते हैं।
+वैकल्पिक संशोधन, जैसे कि [[ कॉकटेल शेकर प्रकार ]] बबल सॉर्ट के प्रदर्शन में सुधार करने की कोशिश करते हैं चूँकि आसपास के आइटमों की समानता और तबादला करने के विचार को एक साथ रखने का विचार बनाए रखते हैं।
 == प्रयोग करें ==
-[[File:Bubble sort animation.gif|thumb|right|280px|बबल सॉर्ट। सूची को कार्तेशियाई निर्देशांक प्रणाली में दर्शाया गया था, हर बिंदु (x, y) का अर्थ है कि मान y अनुक्रम x पर संग्रहित है। फिर हर पिक्सेल के मूल्य के अनुसार बबल सॉर्ट  के माध्यम से सूची को क्रमबद्ध किया गया था। याद रखें कि सबसे बड़ा अंत पहले क्रमबद्ध होता है, छोटे तत्वों को अपनी सही स्थानों पर ले जाने के लिए अधिक समय लगता है।]]यद्यपि बबल सॉर्ट को समझना और लागू करना सबसे सरल सॉर्टिंग एल्गोरिथ्मों में से एक है, लेकिन इसकी O(n<sup>2</sup>) कॉम्प्लेक्सिटी इसकी क्षमता को बहुत ही कम कर देती है जब अधिक संख्या के तत्वों की सूची होती है। सरल O(n<sup>2</sup>) सॉर्टिंग एल्गोरिथमों के बीच, इंसर्शन सॉर्ट जैसे एल्गोरिथम सामान्यतः बहुत अधिक अधिक दक्ष होते हैं।
+[[File:Bubble sort animation.gif|thumb|right|280px|बबल सॉर्ट। सूची को कार्तेशियाई निर्देशांक प्रणाली में दर्शाया गया था, हर बिंदु (x, y) का अर्थ है कि मान y अनुक्रम x पर संग्रहित है। फिर हर पिक्सेल के मूल्य के अनुसार बबल सॉर्ट  के माध्यम से सूची को क्रमबद्ध किया गया था। याद रखें कि सबसे बड़ा अंत पहले क्रमबद्ध होता है, छोटे तत्वों को अपनी सही स्थानों पर ले जाने के लिए अधिक समय लगता है।]]यद्यपि बबल सॉर्ट को समझना और लागू करना सबसे सरल सॉर्टिंग एल्गोरिथ्मों में से एक है, किन्तु इसकी O(n<sup>2</sup>) कॉम्प्लेक्सिटी इसकी क्षमता को बहुत ही कम कर देती है जब अधिक संख्या के तत्वों की सूची होती है। सरल O(n<sup>2</sup>) सॉर्टिंग एल्गोरिथमों के बीच, इंसर्शन सॉर्ट जैसे एल्गोरिथम सामान्यतः बहुत अधिक अधिक दक्ष होते हैं।
-इसकी सादगी के कारण, प्रारंभिक [[कंप्यूटर विज्ञान]] के छात्रों के लिए एक एल्गोरिथ्म, या एक सॉर्टिंग एल्गोरिदम की अवधारणा को पेश करने के लिए अधिकांशतः बबल सॉर्ट का उपयोग किया जाता है। चूंकि, [[ओवेन एस्ट्राचन]] जैसे कुछ शोधकर्ताओं ने कंप्यूटर विज्ञान शिक्षा में बबल सॉर्ट और इसकी निरंतर लोकप्रियता को नापसंद करने के लिए काफी हद तक चले गए हैं, यह सिफारिश की है कि अब इसे पढ़ाया भी नहीं जाता है।<ref name="Astrachan2003" />
+इसकी सादगी के कारण, प्रारंभिक [[कंप्यूटर विज्ञान]] के छात्रों के लिए एक एल्गोरिथ्म, या एक सॉर्टिंग एल्गोरिदम की अवधारणा को प्रस्तुत करने के लिए अधिकांशतः बबल सॉर्ट का उपयोग किया जाता है। चूंकि, [[ओवेन एस्ट्राचन]] जैसे कुछ शोधकर्ताओं ने कंप्यूटर विज्ञान शिक्षा में बबल सॉर्ट और इसकी निरंतर लोकप्रियता को नापसंद करने के लिए अधिक हद तक चले गए हैं, यह सिफारिश की है कि अब इसे पढ़ाया भी नहीं जाता है।<ref name="Astrachan2003" />
 [[शब्दजाल फ़ाइल|जार्गन फ़ाइल]], जो  [[bogosort|बोगोसोर्ट]] को आर्किटेपिकल [एसआईसी] पर्वर्ती घोर एल्गोरिथ्म" कहती है, उसने बबल सॉर्ट को "जेनेरिक बैड एल्गोरिथ्म" कहा।<ref>{{cite web|url=http://www.jargon.net/jargonfile/b/bogo-sort.html|title=jargon, node: bogo-sort}}</ref>[[डोनाल्ड नुथ]], [[कंप्यूटर प्रोग्रामिंग की कला|'द आर्ट ऑफ कंप्यूटर प्रोग्रामिंग']] निष्कर्ष निकालते हुए कि "बबल सॉर्ट कुछ भी सिफ़ारिश करने योग्य नहीं लगता है, एकमात्र एक आकर्षक नाम और यह कि यह कुछ रोचक थियोरेटिकल समस्याओं का समाधान करता है"। जिनमें से कुछ की उन्होंने तब विवेचना की थी।<ref name="Knuth">[[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.)</ref>
-बबल सॉर्ट [[बिग ओ नोटेशन]] के रूप में जाना जाता है और कुछ अन्य सॉर्टिंग एल्गोरिथ्म के साथ तुलना में असंतोषजनक जाना जाता है। विशिष्टता के नजरिए से, विवरण सॉर्ट के समय तुलनात्मक रूप में बबल सॉर्ट से असमान हो सकता है, लेकिन दोनों एल्गोरिथ्मों में स्वैप की आवश्यकता में बहुत अंतर होता है। एस्ट्राकेन जैसे प्रयोगात्मक परिणामों ने यह भी दिखाया है कि इंसर्शन सॉर्ट भी यादृच्छिक सूचियों पर भी काफी बेहतर प्रदर्शन करता है। इन कारणों से, अधिकतर आधुनिक एल्गोरिथ्म पुस्तकों में बबल सॉर्ट का उपयोग इंसर्शन सॉर्ट की तुलना में खास करने के अतिरिक्त कम हो गया है।
+बबल सॉर्ट [[बिग ओ नोटेशन]] के रूप में जाना जाता है और कुछ अन्य सॉर्टिंग एल्गोरिथ्म के साथ समानता में असंतोषजनक जाना जाता है। विशिष्टता के नजरिए से, विवरण सॉर्ट के समय समानतात्मक रूप में बबल सॉर्ट से असमान हो सकता है, किन्तु दोनों एल्गोरिथ्मों में स्वैप की आवश्यकता में बहुत अंतर होता है। एस्ट्राकेन जैसे प्रयोगात्मक परिणामों ने यह भी दिखाया है कि इंसर्शन सॉर्ट भी यादृच्छिक सूचियों पर भी अधिक बेहतर प्रदर्शन करता है। इन कारणों से, अधिकतर आधुनिक एल्गोरिथ्म पुस्तकों में बबल सॉर्ट का उपयोग इंसर्शन सॉर्ट की समानता में खास करने के अतिरिक्त कम हो गया है।
-बबल सॉर्ट आधुनिक सीपीयू हार्डवेयर के साथ भी बुरी प्रकार संघर्ष करता है। यह एक्सेस की तुलना में न्यूनतम दो बार ज्यादा लिखता है जैसा कि इन्सर्शन सॉर्ट करता है, दो बार ज्यादा कैश मिस होते हैं, और असिम्प्टोटिक रूप से और ज्यादा ब्रांच गलतियों का परिणाम होता है।{{citation needed|date=August 2015}}आस्त्राचन  के माध्यम से [[ जावा (प्रोग्रामिंग भाषा) | जावा (प्रोग्रामिंग भाषा)]] में स्ट्रिंग को सॉर्ट करने के अनुभव बबल सॉर्ट को एक [[चयन छांटना]] का अधिकतर पाँचवां भाग और एक सिलेक्शन सॉर्ट का 70% तक तेज होने का दर्शाते हैं।<ref name="Astrachan2003">{{cite journal |last1=Astrachan |first1=Owen |title=Bubble sort: an archaeological algorithmic analysis |url=http://www.cs.duke.edu/~ola/papers/bubble.pdf |journal=ACM SIGCSE Bulletin |volume=35 |issue=1 |year=2003 |pages=1–5 |issn=0097-8418 |doi=10.1145/792548.611918}}</ref>
+बबल सॉर्ट आधुनिक सीपीयू हार्डवेयर के साथ भी बुरी प्रकार संघर्ष करता है। यह एक्सेस की समानता में न्यूनतम दो बार ज्यादा लिखता है जैसा कि इन्सर्शन सॉर्ट करता है, दो बार ज्यादा कैश मिस होते हैं, और असिम्प्टोटिक रूप से और ज्यादा ब्रांच गलतियों का परिणाम होता है।{{citation needed|date=August 2015}}आस्त्राचन  के माध्यम से [[ जावा (प्रोग्रामिंग भाषा) | जावा (प्रोग्रामिंग भाषा)]] में स्ट्रिंग को सॉर्ट करने के अनुभव बबल सॉर्ट को एक [[चयन छांटना]] का अधिकतर पाँचवां भाग और एक सिलेक्शन सॉर्ट का 70% तक तेज होने का दर्शाते हैं।<ref name="Astrachan2003">{{cite journal |last1=Astrachan |first1=Owen |title=Bubble sort: an archaeological algorithmic analysis |url=http://www.cs.duke.edu/~ola/papers/bubble.pdf |journal=ACM SIGCSE Bulletin |volume=35 |issue=1 |year=2003 |pages=1–5 |issn=0097-8418 |doi=10.1145/792548.611918}}</ref>
 कंप्यूटर ग्राफिक्स में, बबल सॉर्ट बहुत छोटी त्रुटियों को भी पकड़ने की क्षमता के लिए लोकप्रिय है (जैसे कि बस दो तत्वों की एक विन्यास विफलता). उदाहरण के लिए, यह एक बहुभुज भरने वाले एल्गोरिदम में उपयोग किया जाता है, जहां बाउंडिंग लाइनें एक विशेष स्कैन लाइन (एक्स-अक्ष के पार) पर उनकी एक्स-अक्ष की अनुक्रमणिका के अनुसार क्रमबद्ध की जाती हैं, और उनकी y कोऑर्डिनेट बढ़ती है, तब उनके क्रम में परिवर्तन (दो तत्वों के बदले जाने से) एकमात्र दो लाइनों के छेद पर होता है। बबल सॉर्ट एक स्थिर सॉर्ट एल्गोरिथम होता है, जैसे कि इन्सर्शन सॉर्ट।
@@ Line 130: / Line 130: @@
 * पासें दाईं से बाएं की ओर हो सकती हैं, बाईं से दाईं की ओर से अधिक असंगठित आइटम वाली सूचियों के लिए यह अधिक दक्ष होता है।
 * कॉकटेल शेकर सॉर्ट बाईं से दाईं और दाईं से बाईं के पासें को बदलता है।
-* मैं विश्वास नहीं कर सकता कि यह सॉर्ट कर सकता है एक सॉर्टिंग एल्गोरिदम है जो बबल सॉर्ट का गलत संस्करण प्रतीत होता है, लेकिन औपचारिक रूप से सम्मिलन प्रकार के समान काम करने के लिए सिद्ध किया जा सकता है।<ref>{{Cite arXiv|last1=Fung |first1=Stanley P. Y. |title=Is this the simplest (and most surprising) sorting algorithm ever? |date=3 October 2021|arxiv=2110.01111 }}</ref>
+* मैं विश्वास नहीं कर सकता कि यह सॉर्ट कर सकता है एक सॉर्टिंग एल्गोरिदम है जो बबल सॉर्ट का गलत संस्करण प्रतीत होता है, किन्तु औपचारिक रूप से सम्मिलन प्रकार के समान काम करने के लिए सिद्ध किया जा सकता है।<ref>{{Cite arXiv|last1=Fung |first1=Stanley P. Y. |title=Is this the simplest (and most surprising) sorting algorithm ever? |date=3 October 2021|arxiv=2110.01111 }}</ref>
@@ Line 138: / Line 138: @@
 उदाहरण के लिए, डोनाल्ड नुथ मूल्यों को उनके वांछित स्थान पर या उनके सम्मिलन के रूप में वर्णित करता है, जिससे [मूल्य] अपने उचित स्तर पर व्यवस्थित हो जाता है, और सॉर्टिंग की इस विधि को कभी-कभी सिफ्टिंग या सिंकिंग तकनीक कहा जाता है।<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>
-यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग लेकिन समान रूप से मान्य दृष्टिकोणों से मान सकता है:
+यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग किन्तु समान रूप से मान्य दृष्टिकोणों से मान सकता है:
 # बड़े मूल्यों को भारी माना जा सकता है और इसलिए सूची के निचले भाग में उत्तरोत्तर डूबते देखा जा सकता है
 # छोटे मूल्यों को हल्का माना जा सकता है और इसलिए उन्हें सूची के शीर्ष पर उत्तरोत्तर बुलबुले के रूप में देखा जा सकता है।
 == लोकप्रिय संस्कृति में ==
-में, [[Google|गूगल]] के पूर्व सीईओ [[एरिक श्मिट]] ने तत्कालीन राष्ट्रपति पद के उम्मीदवार [[बराक ओबामा]] से एक साक्षात्कार के दौरान दस लाख [[पूर्णांक]]ों को क्रमबद्ध करने के सर्वोत्तम विधियां के बारे में पूछा; ओबामा एक पल के लिए रुके और जवाब दिया: मुझे लगता है कि बबल सॉर्ट जाने का गलत तरीका होगा।<ref>{{Cite magazine|last=Lai Stirland|first=Sarah|date=2007-11-14|title=ओबामा ने पास किया अपना गूगल इंटरव्यू|url=https://www.wired.com/2007/11/obama-elect-me/|access-date=2020-10-27|magazine=Wired}}</ref><ref>{{cite AV media|url=https://www.youtube.com/watch?v=m4yVlPqeZwo|title=Barack Obama &#124; Candidates at Google|date=Nov 14, 2007|people=Barack Obama, Eric Schmidt|language=en|publisher=Talks at Google|location=Mountain View, CA 94043 The Googleplex|time=23:20|access-date=Sep 18, 2019|archive-url=https://web.archive.org/web/20190907131624/https://www.youtube.com/watch?v=m4yVlPqeZwo|archive-date=September 7, 2019|url-status=live|format=Video|medium=YouTube}}</ref>
+में, [[Google|गूगल]] के पूर्व सीईओ [[एरिक श्मिट]] ने तत्कालीन राष्ट्रपति पद के उम्मीदवार [[बराक ओबामा]] से एक साक्षात्कार के समय दस लाख [[पूर्णांक]]ों को क्रमबद्ध करने के सर्वोत्तम विधियां के बारे में पूछा; ओबामा एक पल के लिए रुके और उत्तर दिया: मुझे लगता है कि बबल सॉर्ट जाने का गलत विधि होगा।<ref>{{Cite magazine|last=Lai Stirland|first=Sarah|date=2007-11-14|title=ओबामा ने पास किया अपना गूगल इंटरव्यू|url=https://www.wired.com/2007/11/obama-elect-me/|access-date=2020-10-27|magazine=Wired}}</ref><ref>{{cite AV media|url=https://www.youtube.com/watch?v=m4yVlPqeZwo|title=Barack Obama &#124; Candidates at Google|date=Nov 14, 2007|people=Barack Obama, Eric Schmidt|language=en|publisher=Talks at Google|location=Mountain View, CA 94043 The Googleplex|time=23:20|access-date=Sep 18, 2019|archive-url=https://web.archive.org/web/20190907131624/https://www.youtube.com/watch?v=m4yVlPqeZwo|archive-date=September 7, 2019|url-status=live|format=Video|medium=YouTube}}</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 19:27, 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 19:27, 28 March 2023

विश्लेषण

प्रदर्शन

खरगोश और कछुए

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

कार्यान्वयन

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

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

प्रयोग करें

विविधताएं

नाम पर बहस

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories