बबल सोर्ट

बबल सोर्ट

Static visualization of bubble sort
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

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

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

विश्लेषण

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

प्रदर्शन

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

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

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

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

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

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

विविधताएं

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

नाम पर बहस

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

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

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

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

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

2007 में, गूगल के पूर्व सीईओ एरिक श्मिट ने तत्कालीन राष्ट्रपति पद के उम्मीदवार बराक ओबामा से एक साक्षात्कार के समय दस लाख पूर्णांकों को क्रमबद्ध करने के सर्वोत्तम विधियां के बारे में पूछा; ओबामा एक पल के लिए रुके और उत्तर दिया: मुझे लगता है कि बबल सॉर्ट जाने का गलत विधि होगा।

संदर्भ

• 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)