Bubblई सॉर्ट एल्गोरिथ्म के साथ Python सूची उदाहरण का उपयोग करना

क्या है एक Bubblई सॉर्ट?

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

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

इस में Bubblई छंटाई Python ट्यूटोरियल आपको सीखना होगा:

कार्यान्वयन Bubblई सॉर्ट एल्गोरिथ्म

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

समस्या

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

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

[21,6,9,33,3]

समाधान

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

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

[3,6,9,21,33]

कलन विधि

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

प्रथम पुनरावृति

चरण 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 से बड़ा है, इसलिए हम उनकी स्थिति बदल देते हैं।

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

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

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

तीसरा पुनरावर्तन

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

चौथा पुनरावर्तन

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

Python उदाहरण

निम्नलिखित कोड दिखाता है कि इसे कैसे कार्यान्वित किया जाए Bubblई सॉर्ट एल्गोरिथ्म में Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

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

[6, 9, 21, 3, 33]

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

इसका स्पष्टीकरण Python Bubblई सॉर्ट प्रोग्राम कोड इस प्रकार है

यहाँ,

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

Bubblई सॉर्ट लाभ

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

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

Bubblई प्रकार के नुकसान

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

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

जटिलता विश्लेषण Bubblई क्रमबद्ध करें

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

1) सॉर्ट जटिलता

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

2) समय जटिलता

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

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

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

3) स्थान जटिलता

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

सारांश

• बबल सॉर्ट एल्गोरिथ्म दो आसन्न मानों की तुलना करके तथा यदि बाईं ओर का मान दाईं ओर के मान से कम है तो उन्हें आपस में बदलकर काम करता है।
• बबल सॉर्ट एल्गोरिथ्म को लागू करना अपेक्षाकृत सरल है Pythonआपको बस for loops और if स्टेटमेंट्स का उपयोग करना है।
• बबल सॉर्ट एल्गोरिथ्म द्वारा हल की जाने वाली समस्या यह है कि यह वस्तुओं की एक यादृच्छिक सूची लेता है और उसे एक क्रमबद्ध सूची में बदल देता है।
• डेटा संरचना में बबल सॉर्ट एल्गोरिथ्म सबसे अच्छा प्रदर्शन तब करता है जब सूची पहले से ही सॉर्ट की गई हो, क्योंकि यह न्यूनतम संख्या में पुनरावृत्तियाँ करता है।
• जब सूची उलटे क्रम में हो तो बबल सॉर्ट एल्गोरिथ्म अच्छा प्रदर्शन नहीं करता है।
• बब्बलर सॉर्ट की समय जटिलता O (n .) है²) और स्थान जटिलता O (1)
• बब्बलर सॉर्ट एल्गोरिथ्म शैक्षणिक उद्देश्यों के लिए सबसे उपयुक्त है, न कि वास्तविक दुनिया के अनुप्रयोगों के लिए।
• अनुकूलित बबल सॉर्ट, पहले से सॉर्ट किए गए मानों की जांच करते समय अनावश्यक पुनरावृत्तियों को छोड़ कर एल्गोरिथ्म को अधिक कुशल बनाता है।