छाँटने का मतलब क्या है?
सॉर्टिंग यानी चीज़ों को क्रम में लगाना। क्रम आरोही (छोटे से बड़ा, A से Z) या अवरोही (बड़े से छोटा) हो सकता है।
क्यों छाँटें? छँटी सूची में खोजना तेज़ है (बाइनरी सर्च लगा सकते हैं), पढ़ना आसान है, और सबसे छोटा, सबसे बड़ा या बीच का मान तुरंत मिलता है।
एल्गोरिदम यानी पक्के कदमों की सूची। अलग-अलग सॉर्टिंग एल्गोरिदम एक ही जवाब देते हैं, पर मेहनत अलग-अलग लगती है।
बबल सॉर्ट
सूची में बाएँ से दाएँ चलो। हर पड़ोसी जोड़े की तुलना करो। बायाँ बड़ा हो तो अदला-बदली करो। यह एक पास है। पहले पास के बाद सबसे बड़ी चीज़ बुलबुले की तरह “तैरकर” अंत में पहुँच जाती है।
पास दोहराओ। हर पास एक जगह पहले रुक सकता है। किसी पास में एक भी अदला-बदली न हो तो सूची छँट गई — जल्दी रुक जाओ।
repeat
swapped ← false
for i ← 0 to n − 2
if A[i] > A[i+1] then
swap A[i], A[i+1]
swapped ← true
until swapped = falseसबसे ख़राब स्थिति: लगभग n²/2 तुलनाएँ। लिखना आसान, बड़ी सूची पर धीमा।
इंसर्शन सॉर्ट
पहली चीज़ को एक चीज़ की छँटी सूची मानो। अगली चीज़ उठाओ, उससे बड़ी हर चीज़ के पार बाईं ओर खिसकाओ और वहाँ रख दो। अब छँटा हिस्सा एक बड़ा हो गया। अंत तक दोहराओ।
जब सूची लगभग छँटी हो, तब यह बहुत तेज़ है, और छोटी सूचियों पर अच्छा चलता है। सबसे ख़राब स्थिति (उल्टी सूची): लगभग n²/2 तुलनाएँ।
सिलेक्शन सॉर्ट और काउंटिंग सॉर्ट
सिलेक्शन सॉर्ट: पूरी सूची में सबसे छोटी चीज़ ढूँढो और पहली जगह पर रखो (अदला-बदली)। बाक़ी में सबसे छोटी ढूँढो, दूसरी जगह पर रखो। ऐसे ही आगे। तुलनाएँ हमेशा लगभग n²/2, पर अदला-बदली ज़्यादा से ज़्यादा n − 1।
काउंटिंग सॉर्ट: जब मान छोटी पूर्ण संख्याएँ हों, जैसे 10 में से अंक। आवृत्ति सूची बनाओ: कितने 0, कितने 1, … कितने 10। फिर हर मान को उतनी बार लिख दो जितनी बार गिना। कोई तुलना नहीं!
मर्ज सॉर्ट: बाँटो और जीतो
बाँटो: सूची को दो आधों में तोड़ो। हर आधे को फिर तोड़ो, जब तक हर टुकड़े में एक चीज़ न रहे (एक चीज़ की सूची पहले से छँटी है)।
जोड़ो (merge): दो छँटी सूचियों के आगे वाले मानों को देखो और छोटा वाला उठाओ, बार-बार।
उदाहरण: [2, 5] और [1, 8] जोड़ो: 1 लो, फिर 2, फिर 5, फिर 8 → [1, 2, 5, 8]।
n चीज़ों की सूची लगभग log₂ n बार आधी होती है, और हर स्तर पर जोड़ने में लगभग n तुलनाएँ। इसलिए मर्ज सॉर्ट लगभग n log₂ n तुलनाएँ करता है। इसे जोड़ी गई सूची के लिए अतिरिक्त मेमोरी चाहिए।
तरीक़ों की तुलना
| एल्गोरिदम | तुलनाएँ (बड़ी सूची) | अतिरिक्त मेमोरी | किसके लिए अच्छा |
|---|---|---|---|
| बबल | लगभग n²/2 | नहीं | सीखने, बहुत छोटी सूची |
| इंसर्शन | लगभग n²/2 (लगभग छँटी हो तो कम) | नहीं | छोटी या लगभग छँटी सूची |
| सिलेक्शन | लगभग n²/2 | नहीं | जब कम अदला-बदली चाहिए |
| मर्ज | लगभग n log₂ n | हाँ | बड़ी सूची |
1,000 चीज़ों के लिए: n²/2 = 5,00,000 तुलनाएँ, पर n log₂ n ≈ 10,000। इसीलिए बड़े डेटा पर मर्ज सॉर्ट जीतता है।
करके देखो: हाथ से पत्ते छाँटो
8 ताश के पत्ते (या संख्या लिखी पर्चियाँ) लो। तीन बार छाँटो: बबल, इंसर्शन और मर्ज सॉर्ट से। हर तुलना पर एक लकीर खींचो। किस तरीक़े में सबसे कम लकीरें आईं? फिर 3D के खेल वाले कदम में काउंटर से मिलान करो।
मुख्य सूत्र और परिभाषाएँ
- बबल / इंसर्शन / सिलेक्शन: सबसे ख़राब स्थिति में लगभग n(n − 1)/2 तुलनाएँ
- मर्ज सॉर्ट: लगभग n log₂ n तुलनाएँ
- बबल सॉर्ट: पास k के बाद आख़िरी k चीज़ें अपनी पक्की जगह पर
- सिलेक्शन सॉर्ट: ज़्यादा से ज़्यादा n − 1 अदला-बदली
- मर्ज नियम: दोनों सूचियों के आगे वाले मानों में छोटा उठाओ
- काउंटिंग सॉर्ट: हर मान कितनी बार आया गिनो, फिर क्रम से लिखो
हल किए गए उदाहरण
1. [5, 2, 8, 1, 6] पर बबल सॉर्ट का पहला पास दिखाओ।
5>2 बदलो → [2,5,8,1,6]; 5<8 नहीं; 8>1 बदलो → [2,5,1,8,6]; 8>6 बदलो → [2,5,1,6,8]। पहले पास के बाद [2, 5, 1, 6, 8]; 8 अपनी पक्की जगह पर।
2. [4, 1, 3, 2] पर इंसर्शन सॉर्ट। हर बार डालने के बाद सूची दिखाओ।
1 डालो → [1, 4, 3, 2]। 3 डालो → [1, 3, 4, 2]। 2 डालो → [1, 2, 3, 4]।
3. [7, 3, 9, 1] पर सिलेक्शन सॉर्ट। कितनी अदला-बदली हुई?
सबसे छोटा 1 → 7 से बदलो: [1, 3, 9, 7]। बाक़ी में सबसे छोटा 3, पहले से सही जगह। [9, 7] में सबसे छोटा 7 → बदलो: [1, 3, 7, 9]। 2 अदला-बदली।
4. मर्ज सॉर्ट [6, 2, 7, 3] को कैसे छाँटता है?
तोड़ो: [6, 2] और [7, 3] → [6] [2] [7] [3]। जोड़ो: [2, 6] और [3, 7]। इन्हें जोड़ो: 2, 3, 6, 7 → [2, 3, 6, 7]।
5. अंक [3, 1, 3, 0, 2, 1, 3] (3 में से) को काउंटिंग सॉर्ट से छाँटो।
गिनती: 0→1, 1→2, 2→1, 3→3। लिखो: [0, 1, 1, 2, 3, 3, 3]।
6. 10 चीज़ों पर बबल सॉर्ट सबसे ख़राब स्थिति में कितनी तुलनाएँ करेगा (जल्दी रुके बिना)? मर्ज सॉर्ट लगभग कितनी?
बबल: 9 + 8 + … + 1 = 45। मर्ज: लगभग 10 × log₂10 ≈ 33 (असल में 10 चीज़ों के लिए ज़्यादा से ज़्यादा 25)।
आम गलतियाँ
- बबल सॉर्ट एक पास के बाद रोक देना। एक पास सिर्फ़ सबसे बड़ी चीज़ ठीक करता है।
- मर्ज सॉर्ट में दोनों आधे बिना तुलना के चिपका देना। जोड़ते समय हर बार आगे वाला छोटा मान चुनना है।
- सोचना कि सिलेक्शन सॉर्ट तेज़ है क्योंकि अदला-बदली कम है; तुलनाएँ फिर भी लगभग n²/2 हैं।
- भूल जाना कि बिना अदला-बदली वाला पास मिलते ही बबल सॉर्ट रुक सकता है।