बबल सॉर्ट
बबल सॉर्ट समझाने में सबसे आसान सॉर्टिंग एल्गोरिदम है: दो पड़ोसियों की तुलना करें, ग़लत क्रम में हों तो अदल-बदल दें, और दोहराएँ। लंबी सूचियों पर यह धीमा है, लेकिन इसका हर चरण समझना आसान है, इसलिए इसे देखने के लिए यह क्लासिक पहला एल्गोरिदम है।
मूल विचार
सूची में बाएँ से दाएँ चलें और पड़ोसियों की हर जोड़ी देखें। अगर बायाँ मान दाएँ से बड़ा है, तो उन्हें अदल-बदल दें। अंत तक पहुँचने पर सबसे बड़ा मान पूरे रास्ते आख़िरी जगह तक पहुँच चुका होता है, जैसे बुलबुला सतह पर उठता है। इस एक बार चलने को पास कहते हैं। सूची सॉर्ट होने तक पास दोहराएँ।
एक उदाहरण
5, 1, 4, 2, 8 लें। पहला पास 5 और 1 की तुलना करके उन्हें अदल-बदल देता है, फिर 5 और 4 (अदला-बदली), 5 और 2 (अदला-बदली), और 5 और 8 (कोई अदला-बदली नहीं): 1, 4, 2, 5, 8। अब 8 अपनी अंतिम जगह पर है। दूसरा पास 1 और 4 (कोई अदला-बदली नहीं), 4 और 2 (अदला-बदली) और 4 और 5 (कोई अदला-बदली नहीं) की तुलना करता है: 1, 2, 4, 5, 8। तीसरे पास में एक भी अदला-बदली नहीं होती, इसलिए सूची सॉर्ट हो गई: 9 तुलनाएँ और 4 अदला-बदली।
हर पास एक और मान को उसकी जगह क्यों पहुँचाता है
पास के दौरान, अब तक मिला सबसे बड़ा मान हमेशा साथ चलता है: जैसे ही पास उस तक पहुँचता है, हर तुलना उसे एक जगह और दाईं ओर ले जाती है। इसलिए पहला पास सबसे बड़े मान को आख़िर में रखता है, दूसरा पास दूसरे सबसे बड़े को ठीक उससे पहले, और इसी तरह आगे। पास k के बाद आख़िरी k जगहें तय हो जाती हैं, और अगला पास एक जगह पहले रुक सकता है। इसीलिए पास छोटे होते जाते हैं।
अदला-बदली इनवर्ज़न के बराबर
इनवर्ज़न ऐसे दो मानों की जोड़ी है जो ग़लत क्रम में हैं: कोई बड़ा मान किसी छोटे मान से कहीं पहले। ग़लत क्रम वाले दो पड़ोसियों की अदला-बदली ठीक एक इनवर्ज़न हटाती है और कोई नया नहीं बनाती। इसलिए बबल सॉर्ट ठीक उतनी ही अदला-बदली करता है जितने शुरुआती सूची में इनवर्ज़न हैं, तुलनाएँ चाहे किसी भी क्रम में हों। सॉर्ट की हुई सूची में एक भी नहीं होता; n मानों की उल्टी सूची में n(n − 1)/2 होते हैं, जो सबसे ज़्यादा संभव हैं।
जल्दी रुकना और लागत
अगर पूरे पास में कोई अदला-बदली न हो, तो हर पड़ोसी जोड़ी सही क्रम में है और सूची सॉर्ट हो चुकी है। इसकी जाँच से बबल सॉर्ट सॉर्ट की हुई सूची को n − 1 तुलनाओं के एक ही पास में पूरा कर लेता है। सबसे ख़राब स्थिति में इसे फिर भी n − 1 पास और n(n − 1)/2 तुलनाएँ चाहिए, और औसतन अदला-बदली की संख्या n(n − 1)/4 होती है। दोनों n² के साथ बढ़ते हैं, इसलिए सूची दोगुनी करने पर सॉर्ट में लगभग चार गुना समय लगता है।
बबल सॉर्ट स्थिर है: बराबर मानों की कभी अदला-बदली नहीं होती, इसलिए उनका क्रम बना रहता है। यह बिना अतिरिक्त मेमोरी के अपनी जगह पर सॉर्ट करता है। इंसर्शन सॉर्ट में भी यही गुण हैं और उसे आमतौर पर कम चरण लगते हैं, और मर्ज सॉर्ट व क्विकसॉर्ट में n log n के अनुपात में समय लगता है, जो लंबी सूचियों पर बहुत कम है।
ख़ुद आज़माएँ
ऐप खोलें और चलाएँ दबाएँ, या एक-एक तुलना करके बढ़ने के लिए आगे दबाएँ। जिन दो मानों की तुलना हो रही है वे हाइलाइट होते हैं, अदला-बदली अपने अलग रंग में दिखती है, और अपनी जगह पर पहुँचे मान हरे हो जाते हैं। सबसे ख़राब स्थिति देखने के लिए उल्टी सूची आज़माएँ, कुछ पास के बाद जल्दी रुकना देखने के लिए लगभग सॉर्ट सूची, या ऊपर के उदाहरण की संख्याएँ लिखें।
अक्सर पूछे जाने वाले प्रश्न
बबल सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?
सबसे ख़राब और औसत स्थिति में O(n²): n मानों के लिए n(n − 1)/2 तक तुलनाएँ। जल्दी रुकने के साथ, पहले से सॉर्ट की हुई सूची में O(n) यानी एक पास लगता है। इसे सिर्फ़ O(1) अतिरिक्त मेमोरी चाहिए।
क्या बबल सॉर्ट स्थिर है?
हाँ। यह दो पड़ोसियों की अदला-बदली तभी करता है जब बायाँ सचमुच बड़ा हो, इसलिए बराबर मान कभी एक-दूसरे से आगे नहीं निकलते और अपना मूल क्रम बनाए रखते हैं।
बबल सॉर्ट और इंसर्शन सॉर्ट में क्या अंतर है?
दोनों पड़ोसियों की अदला-बदली करते हैं और दोनों उतनी ही अदला-बदली करते हैं जितने इनवर्ज़न हैं। बबल सॉर्ट बिना सॉर्ट वाले हिस्से पर पूरे पास करता है; इंसर्शन सॉर्ट हर नए मान को बस उतना ही पीछे खिसकाता है जितना ज़रूरी है, इसलिए आमतौर पर कम तुलनाएँ करता है, ख़ासकर लगभग सॉर्ट सूचियों पर।
बबल सॉर्ट कब अच्छा विकल्प है?
ज़्यादातर पढ़ाने के लिए, और बहुत छोटी सूचियों के लिए जहाँ गति से ज़्यादा सरलता मायने रखती है। इससे बड़ी किसी भी चीज़ के लिए आपकी प्रोग्रामिंग भाषा में बना सॉर्ट कहीं ज़्यादा तेज़ है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
बबल सॉर्ट आज़माएँ