बबल सोर्ट

बबल सोर्ट

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 ), यहां, एल्गोरिदम पहले दो तत्वों की तुलना करता है, और 5> 1 के बाद से स्वैप करता है।

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 से स्वैप करें

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 से स्वैप करें

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

दूसरा पास

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 से स्वैप करें

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

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

तीसरा दर्रा

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

कार्यान्वयन

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

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

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

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

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

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

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

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

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

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

प्रयोग करें

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

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

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

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

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

विविधताएं

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

नाम पर बहस

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

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

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

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

संदर्भ

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