Python में Bubble Sort
Adjacent elements को बार-बार swap करके sort करें।
में Bubble Sort क्या है?
समस्या क्या है
Sorting (क्रम से लगाना) हर जगह होती है। यह कैसे काम करती है, यह समझ लें तो आप प्रोग्राम की स्पीड के बारे में बेहतर सोच पाते हैं। Bubble sort को स्टेप-दर-स्टेप समझना सबसे आसान है, इसलिए आमतौर पर पहला उदाहरण यही होता है, भले ही असली प्रोग्राम इससे तेज़ algorithm इस्तेमाल करते हैं।
ऐसे समझें
Bubble sort ऐसा है जैसे बच्चों को लंबाई के हिसाब से लाइन में लगाना, और वो भी सिर्फ़ दो पड़ोसियों की जगह बदलकर। लाइन के साथ चलिए और जहाँ लंबा बच्चा आगे हो, उस जोड़ी की जगह बदल दीजिए। एक बार चलने के बाद सबसे लंबा बच्चा आख़िर तक पहुँच जाता है, जैसे पानी में बुलबुला ऊपर आता है। तब तक दोहराइए जब तक एक पूरे चक्कर में कोई अदला-बदली न हो।
result[index] > result[index + 1]👫 क्या लंबा बच्चा आगे है?result[index], result[index + 1] = ...🔄 दोनों पड़ोसियों की जगह बदलिएfor end in range(len(result) - 1, 0, -1):🚶 लाइन फिर से चलिए, हर बार एक बच्चा कमif not swapped: break✅ पूरे चक्कर में कोई अदला-बदली नहीं: लाइन क्रम में हैBubble sort list में बार-बार चलता है और गलत क्रम वाले पड़ोसी आइटम की जगह बदलता है, जब तक एक पूरे pass में कोई swap न हो। आमतौर पर इसमें O(n²) समय लगता है।
मुख्य बातें
result = values.copy()की वजह से कॉपी सॉर्ट होती है, इसलिए caller (function को बुलाने वाले code) की list नहीं बदलती।if result[index] > result[index + 1]:गलत क्रम वाली जोड़ी की जगह बदलता है।- हर pass के बाद
endछोटा होता जाता है, क्योंकि सबसे बड़ी वैल्यू पहले ही आख़िर में पहुँच चुकी हैं। if not swapped: breakतब जल्दी रोक देता है जब किसी pass में swap न हो, इसलिए सॉर्ट किया हुआ इनपुट एक pass में ख़त्म हो जाता है।
इसका उपयोग कब करें?
- यह सीखना कि तुलना पर आधारित सॉर्टिंग कैसे काम करती है।
- पढ़ाने वाले टूल और visualization में बहुत छोटी list।
- एक pass में जाँचना कि list पहले से सॉर्ट की हुई है या नहीं।
कब ज़रूरत नहीं
- कोई भी असली प्रोग्राम:
sorted()औरlist.sort()कहीं ज़्यादा तेज़ हैं (O(n log n)) और अच्छी तरह टेस्ट किए हुए हैं। - कुछ सौ से ज़्यादा आइटम वाली list: तुलनाओं की संख्या लंबाई के वर्ग के हिसाब से बढ़ती है।
Python में Bubble Sort Visualizer
O(n²)हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
अपेक्षित आउटपुट
[1, 2, 4, 5, 8]
यह कैसे काम करता है
गलत क्रम वाले पड़ोसी swap होते हैं। O(n²) के कारण यह मुख्यतः सीखने के लिए उपयोगी है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
एक index ज़्यादा आगे जाना
जब index आख़िरी जगह पर पहुँचता है, तो result[index + 1] list के अंत से बाहर चला जाता है।
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- Count Inversions Count the out-of-order pairs in a list. कठिन
- सूची का माध्यिका सूची को छांटने के बाद उसका मध्य मान ज्ञात करें। आसान