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

Latest revision as of 12:34, 26 October 2023

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

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

विश्लेषण

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

प्रदर्शन

बबल सॉर्ट में सबसे खराब स्थिति और औसत जटिलता $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²) सॉर्टिंग एल्गोरिथमों के बीच, इंसर्शन सॉर्ट जैसे एल्गोरिथम सामान्यतः बहुत अधिक अधिक दक्ष होते हैं।

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

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

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

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

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

विविधताएं

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

नाम पर बहस

बबल सॉर्ट को कभी-कभी डूबने वाली सॉर्ट के रूप में संदर्भित किया जाता है।^[7]

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

यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग किन्तु समान रूप से मान्य दृष्टिकोणों से मान सकता है:

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

↑ "[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.
↑ ^3.0 ^3.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] "[JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort - Java Bug System". bugs.openjdk.java.net. Retrieved 2020-01-11.

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

[Astrachan2003-3] 3.0 ^3.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.

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

[Knuth-5] 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.)

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

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

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

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

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

@@ Line 1: / Line 1: @@
 {{Short description|Simple comparison sorting algorithm}}
-{{Infobox Algorithm
+'''बबल सॉर्ट''', कभी-कभी सिंकिंग सॉर्ट के रूप में संदर्भित किया जाता है, एक सरल सॉर्टिंग एल्गोरिथ्म है जो बार-बार इनपुट सूची तत्व के माध्यम से कदम उठाता है, वर्तमान तत्व की समानता उसके बाद वाले के साथ करता है, [[स्वैप (कंप्यूटर विज्ञान)]] यदि आवश्यक हो तो उनके मूल्य। सूची के माध्यम से ये पास दोहराए जाते हैं जब तक कि पास के समय कोई स्वैप नहीं किया जाना चाहिए, जिसका अर्थ है कि सूची पूरी प्रकार से क्रमबद्ध हो गई है। एल्गोरिथ्म, जो एक समानता प्रकार है, का नाम सूची के शीर्ष पर बड़े तत्वों के बुलबुले के विधियां के लिए रखा गया है।
-|name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
-|image=Bubblesort-edited-color.svg|
-| caption=Static visualization of bubble sort<ref>{{cite web |last=Cortesi |first=Aldo |title=Visualising Sorting Algorithms |url=https://corte.si/posts/code/visualisingsorting/index.html |date=27 April 2007 |access-date=16 March 2017}}</ref>
-|data=[[Array data structure|Array]]
-|time=<math>O(n^2)</math> comparisons, <math>O(n^2)</math> swaps
-|average-time=<math>O(n^2)</math> comparisons, <math>O(n^2)</math> swaps
-|best-time=<math>O(n)</math> comparisons, <math>O(1)</math> swaps
-|space=<math>O(n)</math> total, <math>O(1)</math> auxiliary
-|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>
+यह सरल एल्गोरिदम वास्तविक दुनिया के उपयोग में खराब प्रदर्शन करता है और प्राथमिक रूप से एक शैक्षिक उपकरण के रूप में उपयोग किया जाता है। [[जल्दी से सुलझाएं|क्विकसॉर्ट]], टाइमसॉर्ट या [[ मर्ज़ सॉर्ट ]] जैसे अधिक कुशल एल्गोरिदम का उपयोग पाइथन और जावा जैसी लोकप्रिय प्रोग्रामिंग भाषाओं में निर्मित सॉर्टिंग लाइब्रेरी  के माध्यम से किया जाता है।<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>
 == विश्लेषण ==
-[[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 ), यहां, एल्गोरिदम पहले दो तत्वों की तुलना करता है, और 5> 1 के बाद से स्वैप करता है।
+:( 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 34: @@
 :( 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 76: / Line 65: @@
 === बबल सॉर्ट का अनुकूलन ===
-बबल सॉर्ट एल्गोरिथ्म को यह देखते हुए अनुकूलित किया जा सकता है कि n-वें पास n-वें सबसे बड़े तत्व को ढूंढता है और इसे अपने अंतिम स्थान पर रखता है। इसलिए, n-वें समय के लिए चलते समय आंतरिक लूप अंतिम n-1 आइटम को देखने से बच सकता है:
+बबल सॉर्ट एल्गोरिथ्म को अनुकूलित किया जा सकता है जो यह देखते हुए किया जाता है कि n-वें पास n-वें बड़ा तत्व खोजता है और इसे अंतिम स्थान पर रखता है। तो, जब एन-वें बार चलता है, तो आंतरिक लूप न से छोटे n-1 आइटमों पर नज़र रखने से बच सकता है:
 <syntaxhighlight lang="pascal">
@@ Line 93: / Line 82: @@
 end procedure
 </syntaxhighlight>
-अधिक आम तौर पर, ऐसा हो सकता है कि एक पास पर एक से अधिक तत्व अपनी अंतिम स्थिति में रखे जाते हैं। विशेष रूप से, प्रत्येक पास के बाद, अंतिम स्वैप के बाद सभी तत्वों को क्रमबद्ध किया जाता है, और फिर से जाँच करने की आवश्यकता नहीं होती है। यह कई तत्वों को छोड़ने की अनुमति देता है, जिसके परिणामस्वरूप तुलनात्मक गणना में लगभग 50% सुधार होता है (हालांकि स्वैप गणना में कोई सुधार नहीं होता है), और बहुत कम जटिलता जोड़ता है क्योंकि नया कोड स्वैप किए गए चर को कम करता है:
+और सामान्यतः, एक ही पास में एक से अधिक तत्व अपनी अंतिम स्थान पर रखे जाने की स्थिति हो सकती है। विशेष रूप से, प्रत्येक पास के बाद, अंतिम स्वैप के बाद सभी तत्व सॉर्ट हो जाते हैं और फिर से जाँच करने की आवश्यकता नहीं होती है। इससे कई तत्वों को छोड़ा जा सकता है, समानता गिनती में अधिकतर 50% की बेहतरी होती है (चूंकि स्वैप की गिनती में कोई सुधार नहीं होता है), और इससे बहुत ही कम पेशेवरता जुड़ती है क्योंकि नई कोड "विनिमयित" चर सम्मलित करता है
-स्यूडोकोड में इसे पूरा करने के लिए, निम्नलिखित लिखा जा सकता है:
+स्यूडोकोड में, निम्नलिखित लिखा जा सकता है
 <syntaxhighlight lang="pascal">
 procedure bubbleSort(A : list of sortable items)
@@ Line 111: / Line 100: @@
 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>
+[[शब्दजाल फ़ाइल|जार्गन फ़ाइल]], जो  [[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>
+बबल सॉर्ट [[बिग ओ नोटेशन]] के रूप में जाना जाता है और कुछ अन्य सॉर्टिंग एल्गोरिथ्म के साथ समानता में असंतोषजनक जाना जाता है। विशिष्टता के नजरिए से, विवरण सॉर्ट के समय समानतात्मक रूप में बबल सॉर्ट से असमान हो सकता है, किन्तु दोनों एल्गोरिथ्मों में स्वैप की आवश्यकता में बहुत अंतर होता है। एस्ट्राकेन जैसे प्रयोगात्मक परिणामों ने यह भी दिखाया है कि इंसर्शन सॉर्ट भी यादृच्छिक सूचियों पर भी अधिक बेहतर प्रदर्शन करता है। इन कारणों से, अधिकतर आधुनिक एल्गोरिथ्म पुस्तकों में बबल सॉर्ट का उपयोग इंसर्शन सॉर्ट की समानता में खास करने के अतिरिक्त कम हो गया है।
-कंप्यूटर ग्राफ़िक्स में बबल सॉर्ट लगभग-सॉर्ट किए गए सरणियों में एक बहुत छोटी त्रुटि (जैसे केवल दो तत्वों की अदला-बदली) का पता लगाने और इसे केवल रैखिक जटिलता (2n) के साथ ठीक करने की क्षमता के लिए लोकप्रिय है। उदाहरण के लिए, इसका उपयोग बहुभुज भरने वाले एल्गोरिदम में किया जाता है, जहां बाउंडिंग लाइनों को उनके एक्स समन्वय द्वारा एक विशिष्ट स्कैन लाइन (एक्स अक्ष के समानांतर एक रेखा) पर क्रमबद्ध किया जाता है और y को बढ़ाने के साथ उनके क्रम में परिवर्तन होता है (दो तत्वों की अदला-बदली होती है) दो पंक्तियों का चौराहा। बबल सॉर्ट एक स्थिर सॉर्ट एल्गोरिथम है, जैसे सम्मिलन सॉर्ट।
+बबल सॉर्ट आधुनिक सीपीयू हार्डवेयर के साथ भी बुरी प्रकार संघर्ष करता है। यह एक्सेस की समानता में न्यूनतम दो बार ज्यादा लिखता है जैसा कि इन्सर्शन सॉर्ट करता है, दो बार ज्यादा कैश मिस होते हैं, और असिम्प्टोटिक रूप से और ज्यादा ब्रांच गलतियों का परिणाम होता है।{{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 कोऑर्डिनेट बढ़ती है, तब उनके क्रम में परिवर्तन (दो तत्वों के बदले जाने से) एकमात्र दो लाइनों के छेद पर होता है। बबल सॉर्ट एक स्थिर सॉर्ट एल्गोरिथम होता है, जैसे कि इन्सर्शन सॉर्ट।
 == विविधताएं ==
-* ऑड-ईवन सॉर्ट, मैसेज पासिंग सिस्टम के लिए बबल सॉर्ट का समानांतर संस्करण है।
+* ऑड-ईवन सॉर्ट, बबल सॉर्ट का एक समान्तर संस्करण है, मैसेज-पासिंग सिस्टम के लिए।
-* पास बाएं से दाएं के बजाय दाएं से बाएं हो सकते हैं। यह अंत में जोड़े गए अनसोर्टेड आइटम वाली सूचियों के लिए अधिक कुशल है।
+* पासें दाईं से बाएं की ओर हो सकती हैं, बाईं से दाईं की ओर से अधिक असंगठित आइटम वाली सूचियों के लिए यह अधिक दक्ष होता है।
-* कॉकटेल शेकर सॉर्ट बारी-बारी से बायीं ओर और दायीं ओर गुजरता है।
+* कॉकटेल शेकर सॉर्ट बाईं से दाईं और दाईं से बाईं के पासें को बदलता है।
-* मैं विश्वास नहीं कर सकता कि यह सॉर्ट कर सकता है एक सॉर्टिंग एल्गोरिदम है जो बबल सॉर्ट का गलत संस्करण प्रतीत होता है, लेकिन औपचारिक रूप से सम्मिलन प्रकार के समान काम करने के लिए सिद्ध किया जा सकता है।<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>
 == नाम पर बहस ==
 बबल सॉर्ट को कभी-कभी डूबने वाली सॉर्ट के रूप में संदर्भित किया जाता है।<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>
-यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग लेकिन समान रूप से मान्य दृष्टिकोणों से मान सकता है:
+यह बहस आसानी से कायम है जिसके साथ कोई इस एल्गोरिथम को दो अलग-अलग किन्तु समान रूप से मान्य दृष्टिकोणों से मान सकता है:
 # बड़े मूल्यों को भारी माना जा सकता है और इसलिए सूची के निचले भाग में उत्तरोत्तर डूबते देखा जा सकता है
 # छोटे मूल्यों को हल्का माना जा सकता है और इसलिए उन्हें सूची के शीर्ष पर उत्तरोत्तर बुलबुले के रूप में देखा जा सकता है।
 == लोकप्रिय संस्कृति में ==
-में, [[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>
@@ Line 155: / Line 148: @@
 ==बाहरी संबंध==
-{{wikibooks|Algorithm implementation|Sorting/Bubble_sort|Bubble sort}}
-{{commons category|Bubble sort}}
-{{wikiversity|Bubble sort}}
 * {{cite web |last=Martin |first=David R. |url=http://www.sorting-algorithms.com/bubble-sort |archive-date=2015-03-03 |archive-url=https://web.archive.org/web/20150303084352/http://www.sorting-algorithms.com/bubble-sort |date=2007 |title=Animated Sorting Algorithms: Bubble Sort}} – graphical demonstration
 * {{cite web | url= http://lecture.ecc.u-tokyo.ac.jp/~ueda/JavaApplet/BubbleSort.html |title= Lafore's Bubble Sort}} (Java applet animation)
 * {{OEIS el|1=A008302|2=Table (statistics) of the number of permutations of <nowiki>[n]</nowiki> that need k pair-swaps during the sorting|formalname=Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1)}}
-{{sorting}}
-[[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: छँटाई एल्गोरिदम]] [[Category: तुलना प्रकार]] [[Category: स्थिर प्रकार]]
 [[no:Sorteringsalgoritme#Boblesortering]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with unsourced statements from August 2015]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:CS1 maint]]
+[[Category:Citation Style 1 templates|M]]
+[[Category:Collapse templates]]
+[[Category:Commons category link is locally defined]]
 [[Category:Created On 21/03/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates based on the Citation/CS1 Lua module]]
+[[Category:Templates generating COinS|Cite magazine]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia fully protected templates|Cite magazine]]
+[[Category:Wikipedia metatemplates]]
+[[Category:छँटाई एल्गोरिदम]]
+[[Category:तुलना प्रकार]]
+[[Category:स्थिर प्रकार]]
+[[Category:स्यूडोकोड के उदाहरण वाले लेख]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 12:34, 26 October 2023

Contents

विश्लेषण

प्रदर्शन

खरगोश और कछुए

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

कार्यान्वयन

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

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

प्रयोग करें

विविधताएं

नाम पर बहस

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 12:34, 26 October 2023

विश्लेषण

प्रदर्शन

खरगोश और कछुए

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

कार्यान्वयन

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

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

प्रयोग करें

विविधताएं

नाम पर बहस

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories