सूची उदाहरण का उपयोग करके अजगर के साथ बबल सॉर्ट एल्गोरिथम

एक बुलबुला सॉर्ट क्या है?

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

यह प्रक्रिया तब तक दोहराई जाती है जब तक कि किसी सूची के सभी मूल्यों की तुलना और यदि आवश्यक हो तो अदला-बदली नहीं की जाती है। प्रत्येक पुनरावृत्ति को आमतौर पर पास कहा जाता है। एक बुलबुला सॉर्ट में पास की संख्या एक सूची ऋण में तत्वों की संख्या के बराबर है।

पायथन ट्यूटोरियल में इस बबल सॉर्टिंग में आप सीखेंगे:

• एक बुलबुला सॉर्ट क्या है?
• बुलबुला सॉर्ट एल्गोरिथ्म को लागू करना
• अनुकूलित बबल सॉर्ट एल्गोरिथम
• दृश्य प्रतिनिधित्व
• पायथन उदाहरण
• कोड स्पष्टीकरण
• बबल सॉर्ट के फायदे
• बबल सॉर्ट नुकसान
• बबल सॉर्ट की जटिलता विश्लेषण

बुलबुला सॉर्ट एल्गोरिथ्म को लागू करना

हम कार्यान्वयन को तीन (3) चरणों में तोड़ देंगे, अर्थात् समस्या, समाधान और एल्गोरिथ्म जिसे हम किसी भी भाषा में कोड लिखने के लिए उपयोग कर सकते हैं।

समस्या

मदों की एक सूची यादृच्छिक क्रम में दी गई है, और हम एक क्रमबद्ध तरीके से वस्तुओं की व्यवस्था करना चाहते हैं

निम्नलिखित सूची पर विचार करें:

[21,6,9,33,3]

समाधान

सूची के माध्यम से दो आसन्न तत्वों की तुलना करें और यदि पहला मान दूसरे मूल्य से अधिक है तो उन्हें स्वैप करें।

परिणाम निम्नानुसार होना चाहिए:

[3,6,9,21,33]

कलन विधि

बबल सॉर्ट एल्गोरिथ्म निम्नानुसार काम करता है

चरण 1) तत्वों की कुल संख्या प्राप्त करें। दी गई सूची में वस्तुओं की कुल संख्या प्राप्त करें

चरण 2) बाहरी पास (एन - 1) की संख्या निर्धारित करें। इसकी लंबाई सूची शून्य से एक है

चरण 3) बाहरी पास के लिए आंतरिक पास (n - 1) बार प्रदर्शन करें। पहला तत्व मान प्राप्त करें और दूसरे मूल्य के साथ तुलना करें। यदि दूसरा मान पहले मान से कम है, तो पदों को स्वैप करें

चरण 4) चरण 3 को दोहराएं जब तक आप बाहरी पास (एन - 1) तक नहीं पहुंच जाते। सूची में अगला तत्व प्राप्त करें फिर चरण 3 में निष्पादित की गई प्रक्रिया को दोहराएं जब तक कि सभी मानों को उनके सही आरोही क्रम में नहीं रखा गया हो।

चरण 5) सभी पास होने पर परिणाम लौटाएं। क्रमबद्ध सूची के परिणाम लौटाएं

चरण 6) एल्गोरिथ्म का अनुकूलन

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

अनुकूलित बबल सॉर्ट एल्गोरिथम

डिफ़ॉल्ट रूप से, पायथन में बबल सॉर्ट के लिए एल्गोरिथ्म सूची में सभी वस्तुओं की तुलना करता है, भले ही सूची पहले से सॉर्ट की गई हो या नहीं। यदि दी गई सूची पहले से ही क्रमबद्ध है, तो सभी मूल्यों की तुलना करना समय और संसाधनों की बर्बादी है।

बबल सॉर्ट का अनुकूलन हमें अनावश्यक पुनरावृत्तियों से बचने और समय और संसाधनों को बचाने में मदद करता है।

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

अनुकूलन निम्नलिखित चरणों का उपयोग करके किया जाता है

चरण 1) एक ध्वज चर बनाएं जो मॉनिटर करता है कि क्या आंतरिक लूप में कोई स्वैपिंग हुई है

चरण 2) यदि मानों की स्थिति बदली गई है, तो अगली पुनरावृत्ति जारी रखें

चरण 3) यदि लाभ ने पदों की अदला-बदली नहीं की है, तो आंतरिक लूप को समाप्त करें, और बाहरी लूप के साथ जारी रखें।

एक अनुकूलित बबल सॉर्ट अधिक कुशल है क्योंकि यह केवल आवश्यक चरणों को निष्पादित करता है और जिनकी आवश्यकता नहीं है उन्हें छोड़ देता है।

दृश्य प्रतिनिधित्व

पांच तत्वों की सूची को देखते हुए, निम्न चित्र बताते हैं कि कैसे छंटाई करते समय बुलबुले मूल्यों के माध्यम से पुनरावृत्त होते हैं

निम्न छवि अनसोल्ड सूची को दिखाती है

पहला Iteration

चरण 1)

21 और 6 के मान की तुलना यह जांचने के लिए की जाती है कि कौन सा दूसरे से अधिक है।

21 6 से अधिक है, इसलिए 21 ने 6 पर कब्जा कर लिया है, जबकि 6 वह स्थान लेता है जो 21 द्वारा कब्जा कर लिया गया था

हमारी संशोधित सूची अब ऊपर वाले की तरह दिखती है।

चरण 2)

21 और 9 के मूल्यों की तुलना की जाती है।

21 9 से अधिक है, इसलिए हम 21 और 9 के पदों को स्वैप करते हैं

नई सूची अब ऊपर है

चरण 3)

21 और 33 के मानों की तुलना अधिक से अधिक खोजने के लिए की जाती है।

33 मान 21 से अधिक है, इसलिए कोई स्वैपिंग नहीं होती है।

चरण 4)

33 और 3 के मानों की तुलना अधिक से अधिक खोजने के लिए की जाती है।

33 मान 3 से अधिक है, इसलिए हम उनके पदों को स्वैप करते हैं।

पहले पुनरावृत्ति के अंत में क्रमबद्ध सूची ऊपर की तरह है

दूसरा पुनरावृत्ति

दूसरी पुनरावृत्ति के बाद नई सूची इस प्रकार है

थर्ड इटरेशन

तीसरी पुनरावृत्ति के बाद नई सूची इस प्रकार है

चौथा Iteration

चौथी पुनरावृत्ति के बाद नई सूची इस प्रकार है

पायथन उदाहरण

निम्न कोड दिखाता है कि पायथन में बबल सॉर्ट एल्गोरिथ्म को कैसे लागू किया जाए।

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

पायथन में उपरोक्त बबल सॉर्ट प्रोग्राम को निष्पादित करना निम्नलिखित परिणाम उत्पन्न करता है

[6, 9, 21, 3, 33]

कोड स्पष्टीकरण

पायथन बबल सॉर्ट प्रोग्राम कोड के लिए स्पष्टीकरण निम्नानुसार है

यहां,

1. एक फ़ंक्शन बबल को परिभाषित करता है जो कि पैरामीटर को स्वीकार करता है। कोड कुछ भी आउटपुट नहीं करता है।
2. सरणी की लंबाई हो जाती है और एक चर n के लिए मान प्रदान करता है। कोड कुछ भी आउटपुट नहीं करता है
3. एक लूप के लिए शुरू होता है जो बबल सॉर्ट एल्गोरिथ्म (एन - 1) बार चलाता है। यह बाहरी लूप है। कोड कुछ भी आउटपुट नहीं करता है
4. एक ध्वज चर को परिभाषित करता है जिसका उपयोग यह निर्धारित करने के लिए किया जाएगा कि क्या स्वैप हुआ है या नहीं। यह अनुकूलन उद्देश्यों के लिए है। कोड कुछ भी आउटपुट नहीं करता है
5. आंतरिक लूप को शुरू करता है जो सूची में सभी मानों की तुलना पहले से अंतिम एक तक करता है। कोड कुछ भी आउटपुट नहीं करता है।
6. यदि बाएं हाथ की तरफ का मान तत्काल दाईं ओर एक से अधिक है, तो यह जांचने के लिए कि यदि कथन का उपयोग किया जाता है। कोड कुछ भी आउटपुट नहीं करता है।
7. यदि स्थिति सही का मूल्यांकन करती है, तो टेम्पोरल वैरिएबल tmp को theSeq [j] का मान असाइन करता है। कोड कुछ भी आउटपुट नहीं करता है
8. TheSeq [j + 1] का मान TheSeq [j] की स्थिति को सौंपा गया है। कोड कुछ भी आउटपुट नहीं करता है
9. वैरिएबल tmp का मान स्थिति को निर्धारित करने के लिए सौंपा गया है [j + 1]। कोड कुछ भी आउटपुट नहीं करता है
10. फ्लैग वैरिएबल को मान 1 सौंपा गया है ताकि यह संकेत मिल सके कि स्वैप हुआ है। कोड कुछ भी आउटपुट नहीं करता है
11. यदि चर ध्वज का मान 0. है, तो यह जांचने के लिए कि यदि आउटपुट कुछ भी नहीं है, तो एक स्टेटमेंट का उपयोग करता है
12. यदि मान 0 है, तो हम ब्रेक स्टेटमेंट को कहते हैं जो आंतरिक लूप से बाहर निकलता है।
13. सॉर्ट किए जाने के बाद TheSeq का मान लौटाता है। कोड सॉर्ट की गई सूची को आउटपुट करता है।
14. एक चर एल को परिभाषित करता है जिसमें यादृच्छिक संख्याओं की एक सूची होती है। कोड कुछ भी आउटपुट नहीं करता है।
15. एक चर परिणाम के लिए फ़ंक्शन बबलसॉर्ट का मान असाइन करता है।
16. चर परिणाम का मूल्य प्रिंट करता है।

बबल सॉर्ट के फायदे

बबल सॉर्ट एल्गोरिथ्म के कुछ फायदे निम्नलिखित हैं

• यह समझना आसान है
• यह बहुत अच्छा प्रदर्शन करता है जब सूची पहले से ही या लगभग हल हो जाती है
• इसमें व्यापक मेमोरी की आवश्यकता नहीं होती है।
• एल्गोरिथ्म के लिए कोड लिखना आसान है
• अन्य छँटाई एल्गोरिदम की तुलना में अंतरिक्ष की आवश्यकताएँ न्यूनतम हैं।

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

बबल सॉर्ट एल्गोरिथ्म के कुछ नुकसान निम्नलिखित हैं

• बड़ी सूचियों को छांटने पर यह अच्छा प्रदर्शन नहीं करता है। इसमें बहुत अधिक समय और संसाधन लगते हैं।
• इसका उपयोग ज्यादातर अकादमिक उद्देश्यों के लिए किया जाता है न कि वास्तविक दुनिया के अनुप्रयोग के लिए।
• सूची को क्रमबद्ध करने के लिए आवश्यक चरणों की संख्या क्रम n ^{2 है}

बबल सॉर्ट की जटिलता विश्लेषण

जटिलता के तीन प्रकार हैं:

1) क्रमबद्ध जटिलता

सॉर्ट कॉम्प्लेक्सिटी का उपयोग निष्पादन समय और स्थान की मात्रा को व्यक्त करने के लिए किया जाता है जो सूची को सॉर्ट करने के लिए लेता है। बबल सॉर्ट उस सूची को सॉर्ट करने के लिए (n - 1) पुनरावृत्तियों बनाता है जहां n सूची में तत्वों की कुल संख्या है।

2) समय जटिलता

बबल सॉर्ट की समय जटिलता O (n ² ) है

समय की जटिलताओं को इस प्रकार वर्गीकृत किया जा सकता है:

• सबसे खराब स्थिति - यह वह जगह है जहां प्रदान की गई सूची अवरोही क्रम में है। एल्गोरिथ्म अधिकतम निष्पादित करता है जिसे [बिग-ओ] ओ (एन ² ) के रूप में व्यक्त किया जाता है।
• सर्वश्रेष्ठ मामला - यह तब होता है जब प्रदान की गई सूची पहले से ही सॉर्ट की जाती है। एल्गोरिथ्म निष्पादन की न्यूनतम संख्या करता है जिसे [बिग-ओमेगा] n (n) के रूप में व्यक्त किया जाता है
• औसत मामला - यह तब होता है जब सूची यादृच्छिक क्रम में होती है। औसत जटिलता को [बिग-थीटा] n (n ² ) के रूप में दर्शाया गया है

3) अंतरिक्ष जटिलता

अंतरिक्ष जटिलता सूची को सॉर्ट करने के लिए आवश्यक अतिरिक्त स्थान की मात्रा को मापती है। बबल सॉर्ट को केवल स्वैपिंग मानों के लिए उपयोग किए जाने वाले लौकिक चर के लिए एक (1) अतिरिक्त स्थान की आवश्यकता होती है। इसलिए, इसमें O (1) की एक अंतरिक्ष जटिलता है।

सारांश

• बबल सॉर्ट एल्गोरिथ्म दो आसन्न मूल्यों की तुलना करके और उन्हें स्वैप करके काम करता है यदि बाईं तरफ का मूल्य दाईं ओर के मूल्य से कम है।
• एक बुलबुला सॉर्ट एल्गोरिथ्म को लागू करना पायथन के साथ अपेक्षाकृत सीधे आगे है। आप सभी का उपयोग करने की जरूरत है छोरों और अगर बयान के लिए कर रहे हैं।
• बुलबुला सॉर्ट एल्गोरिथ्म हल करती है कि समस्या वस्तुओं की एक यादृच्छिक सूची ले रही है और इसे एक आदेशित सूची में बदल रही है।
• डेटा संरचना में बुलबुला सॉर्ट एल्गोरिथ्म सबसे अच्छा प्रदर्शन करता है जब सूची पहले से ही क्रमबद्ध होती है क्योंकि यह पुनरावृत्तियों की एक न्यूनतम संख्या करता है।
• बुलबुला क्रम एल्गोरिथ्म अच्छा प्रदर्शन नहीं करता है जब सूची रिवर्स ऑर्डर में होती है।
• बब्लर सॉर्ट में O (n ² ) की समय जटिलता और O ( ¹ ) की एक अंतरिक्ष जटिलता है
• बब्लर सॉर्ट एल्गोरिथ्म शैक्षिक उद्देश्यों के लिए सबसे उपयुक्त है और वास्तविक दुनिया अनुप्रयोगों के लिए नहीं।
• अनुकूलित बबल सॉर्ट एल्गोरिथ्म को अनावश्यक पुनरावृत्तियों को छोड़ कर अधिक कुशल बनाता है जब पहले से छंटे हुए मानों की जांच की जाती है।