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

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

बबल सॉर्ट कैसे काम करता है?

बबल सॉर्ट में, दो फॉर लूप्स का उपयोग किया जाता है। बाहरी फॉर लूप लिस्ट पर इटरेट करता है। आंतरिक फॉर लूप सभी बाहरी लूप इटरेशन्स के लिए लिस्ट पर इटरेट करता है।

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

हम एक उदाहरण की मदद से बेहतर समझ सकते हैं।

उदाहरण

हमें निम्नलिखित लिस्ट को सॉर्ट करने की आवश्यकता है।

आउटर लूप = 1

5 > 2, इसलिए दोनों को स्वैप करें

5 > 1, इसलिए दोनों को स्वैप करें

5 > 3, इसलिए दोनों को स्वैप करें

5 > 4, इसलिए दोनों को स्वैप करें

(पहले आउटर इटरेशन के बाद सबसे बड़ा एलिमेंट 5 अंतिम इंडेक्स पर पहुंच गया है)

आउटर लूप = 2

2 > 1, इसलिए स्वैप करें

स्वैपिंग की आवश्यकता नहीं

स्वैपिंग की आवश्यकता नहीं

जैसा कि हम देख सकते हैं लिस्ट दूसरे आउटर इटरेशन में ही सॉर्ट हो गई है। लेकिन आउटर लूप 3 और बार इटरेट करेगा बिना किसी स्वैप ऑपरेशन के। इसलिए, उदाहरण में केवल 2 इटरेशन दिखाए गए हैं। कभी-कभी लिस्ट पहले इटरेशन में ही सॉर्ट हो सकती है। कभी-कभी लिस्ट अंतिम इटरेशन में सॉर्ट हो सकती है। इस प्रकार, आउटर लूप हमेशा n बार इटरेट करेगा।

उदाहरण

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

array = [2, 3, 1, 5, 4]
print(bubble_sort(array))

आउटपुट

[1, 2, 3, 4, 5]