बबल सॉर्ट एक सूची को आरोही (या अवरोही) क्रम में सॉर्ट करने के लिए एक सॉर्टिंग एल्गोरिदम है। यह सबसे आसान छँटाई एल्गोरिथ्म है लेकिन यह बहुत कुशल नहीं है। इसका उपयोग छोटे इनपुट आकारों पर किया जा सकता है लेकिन बड़ी लंबाई वाली सूचियों या सरणियों के लिए समय कुशल नहीं है। इसकी समय जटिलता ओ (एन ^ 2) है। हालाँकि, यह एक इन-प्लेस सॉर्टिंग एल्गोरिथम है, जिसका अर्थ है कि यह किसी अतिरिक्त स्थान का उपयोग नहीं करता है। इस प्रकार, अंतरिक्ष जटिलता के मामले में इसकी कुशल। हालांकि, इसका अधिक उपयोग नहीं किया जाता है क्योंकि बबल सॉर्ट की तुलना में बेहतर सॉर्टिंग एल्गोरिदम हैं।
बबल सॉर्ट कैसे काम करता है?
बबल सॉर्ट में, लूप के लिए दो का उपयोग किया जाता है। लूप के लिए बाहरी सूची में पुनरावृत्त होता है। लूप के लिए आंतरिक भी सभी बाहरी लूप पुनरावृत्तियों के लिए सूची में पुनरावृति करता है।
बबल सॉर्ट में मुख्य ऑपरेशन दो लगातार तत्वों की तुलना करना है। यदि पहला तत्व अगले तत्व से बड़ा है, तो दोनों को स्वैप करें, ताकि छोटा तत्व आगे आए और बड़ा तत्व वापस चला जाए। बाहरी लूप के एक पुनरावृत्ति में, सूची का सबसे बड़ा तत्व अंतिम सूचकांक पर जाता है। बाहरी लूप के दूसरे पुनरावृत्ति में, सूची का दूसरा सबसे बड़ा तत्व दूसरे अंतिम सूचकांक पर जाता है और इसी तरह। इसलिए, हम सभी पुनरावृत्तियों के अंत में क्रमबद्ध सूची प्राप्त करते हैं।
हम एक उदाहरण की मदद से बेहतर ढंग से समझ सकते हैं।
उदाहरण
हमें निम्न सूची को क्रमबद्ध करना आवश्यक है।
| 5 | 2 | 1 | 3 | 4 |
बाहरी लूप=1
| 5 | 2 | 1 | 3 | 4 |
5>2, इसलिए दोनों को स्वैप करें
| 2 | 5 | 1 | 3 | 4 |
5>1, इसलिए दोनों को स्वैप करें
| 2 | 1 | 5 | 3 | 4 |
5>3, इसलिए दोनों को स्वैप करें
| 2 | 1 | 3 | 5 | 4 |
5>4, इसलिए दोनों को स्वैप करें
| 2 | 1 | 3 | 5 | 4 |
(सबसे बड़ा तत्व 5 पहले बाहरी पुनरावृत्ति के बाद अंतिम सूचकांक पर पहुंच गया है)
बाहरी लूप=2
| 2 | 1 | 3 | 5 | 4 |
2>1, इसलिए स्वैप करें
| 1 | 2 | 3 | 5 | 4 |
किसी अदला-बदली की आवश्यकता नहीं है
| 1 | 2 | 3 | 4 | 5 |
किसी अदला-बदली की आवश्यकता नहीं है
| 1 | 2 | 3 | 4 | 5 |
जैसा कि हम देख सकते हैं कि सूची को दूसरे बाहरी पुनरावृत्ति में ही क्रमबद्ध किया गया है। लेकिन बाहरी लूप बिना किसी स्वैप ऑपरेशन के 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]