खोज और छँटाई एल्गोरिदम क्या हैं?
एल्गोरिदम किसी समस्या को हल करने के साफ़ चरणों की सूची है। कंप्यूटर में दो काम बार-बार आते हैं:
- खोज (searching): क्या कोई मान सूची में है, और कहाँ?
- छँटाई (sorting): सूची को क्रम में लगाना — छोटे से बड़ा (आरोही) या बड़े से छोटा (अवरोही)।
एल्गोरिदम की तुलना तुलनाओं की गिनती से करते हैं (कितनी बार दो मान जाँचे)। कम तुलना = तेज़ एल्गोरिदम।
रेखीय खोज (Linear search)
पहले आइटम से शुरू करो, लक्ष्य से मिलाओ। मिल गया तो रुको, नहीं तो अगले पर जाओ। अंत तक न मिले तो आइटम सूची में नहीं है।
for i from 0 to length − 1
if list[i] = target then return i
return "not found"- किसी भी सूची पर चलती है, छँटी हो या नहीं।
- लिखना आसान।
- बड़ी सूची में धीमी: n आइटम में n तुलनाएँ तक (सबसे बुरी स्थिति)।
द्विआधारी खोज (Binary search)
यह सिर्फ़ छँटी सूची पर चलती है।
- बीच वाला आइटम देखो।
- वही लक्ष्य है तो रुको।
- लक्ष्य छोटा है तो बायाँ आधा रखो, बड़ा है तो दायाँ आधा।
- बचे हुए आधे पर दोहराओ, जब तक मिल न जाए या कुछ न बचे।
low ← 0, high ← length − 1
while low ≤ high
mid ← (low + high) DIV 2
if list[mid] = target then return mid
else if list[mid] < target then low ← mid + 1
else high ← mid − 1
return "not found"हर जाँच सूची आधी कर देती है। 1,000 आइटम में लगभग 10 जाँच, 10 लाख में लगभग 20। रेखीय खोज में 10 लाख तक लग सकती हैं।
बबल सॉर्ट और मर्ज सॉर्ट
बबल सॉर्ट
सूची में हर पड़ोसी जोड़े की तुलना करो; गलत क्रम हो तो अदला-बदली। एक चक्कर (pass) के बाद सबसे बड़ा आइटम अंत में पहुँच जाता है। तब तक चक्कर लगाओ जब तक किसी चक्कर में एक भी अदला-बदली न हो। आसान है, कम मेमोरी लेता है, पर बड़ी सूची में धीमा (लगभग n² तुलनाएँ)।
मर्ज सॉर्ट
बाँटो और जीतो (divide and conquer) तरीका। सूची को बार-बार आधा करो जब तक हर टुकड़े में एक आइटम न बचे (एक आइटम अपने-आप छँटा है)। फिर टुकड़ों को जोड़ो (merge): दोनों के आगे वाले आइटम मिलाओ, छोटा पहले लो। बड़ी सूची में बहुत तेज़ (लगभग n·log₂n), पर ज़्यादा मेमोरी लेता है।
इंसर्शन सॉर्ट
आइटम एक-एक उठाओ और छँटे हिस्से में सही जगह खिसकाओ, जैसे हाथ में ताश के पत्ते लगाते हैं। छोटी या लगभग छँटी सूची के लिए अच्छा।
कौन-सा एल्गोरिदम कब?
| एल्गोरिदम | छँटी सूची चाहिए? | बड़ी सूची में गति | किसके लिए अच्छा |
|---|---|---|---|
| रेखीय खोज | नहीं | धीमी (n) | छोटी या बिना छँटी सूची |
| द्विआधारी खोज | हाँ | बहुत तेज़ (log₂n) | बड़ी छँटी सूची |
| बबल सॉर्ट | — | धीमा (n²) | बहुत छोटी सूची, सीखने के लिए |
| मर्ज सॉर्ट | — | तेज़ (n log n) | बड़ी सूची |
सुझाव: अगर एक ही सूची में बार-बार खोजना है, तो एक बार छाँट लो और फिर द्विआधारी खोज करो।
करके देखो: पत्तों की खोज-दौड़
1 से 16 तक कार्ड बनाओ। उन्हें मिलाकर उल्टा लाइन में रखो और दोस्त से 11 ढूँढने को कहो, एक बार में एक पत्ता पलटकर (रेखीय खोज)। गिनो कितनी बार पलटा। अब क्रम में रखकर हर बार बीच वाला पलटो (द्विआधारी खोज)। किसमें कम बार लगा? फिर मिले हुए पत्तों को बबल सॉर्ट से छाँटो और अदला-बदली गिनो।
मुख्य सूत्र और परिभाषाएँ
- रेखीय खोज (सबसे बुरी स्थिति): n तुलनाएँ
- द्विआधारी खोज (सबसे बुरी स्थिति): लगभग log₂n + 1 तुलनाएँ
- mid = (low + high) DIV 2
- बबल सॉर्ट: n − 1 चक्कर तक, लगभग n²/2 तुलनाएँ
- मर्ज सॉर्ट: लगभग n·log₂n तुलनाएँ
हल किए गए उदाहरण
1. [42, 7, 19, 88, 3, 56] में 56 की रेखीय खोज। कितनी तुलनाएँ?
42, 7, 19, 88, 3, 56 → छठी जाँच में मिला: 6 तुलनाएँ।
2. [3, 7, 11, 19, 23, 35, 42, 56, 64, 71, 88, 90] में 64 की द्विआधारी खोज।
low 0, high 11 → mid 5 = 35 < 64 → low 6। mid 8 = 64 → मिल गया। 2 तुलनाएँ।
3. [5, 1, 4, 2] पर बबल सॉर्ट का एक चक्कर।
5>1 बदलो → [1,5,4,2]; 5>4 बदलो → [1,4,5,2]; 5>2 बदलो → [1,4,2,5]। 5 अंत में पहुँचा।
4. [2, 9] और [4, 5] को मर्ज करो।
2 vs 4 → 2; 9 vs 4 → 4; 9 vs 5 → 5; फिर 9। नतीजा [2, 4, 5, 9]।
5. 64 आइटम पर द्विआधारी खोज में ज़्यादा से ज़्यादा कितनी जाँच?
64 → 32 → 16 → 8 → 4 → 2 → 1: 6 बार आधा, तो अधिकतम 7 जाँच।
6. [9, 2, 7, 4] पर द्विआधारी खोज क्यों नहीं?
सूची छँटी नहीं है, तो आधा फेंकने पर लक्ष्य भी फेंका जा सकता है। पहले छाँटो या रेखीय खोज करो।
आम गलतियाँ
- बिना छँटी सूची पर द्विआधारी खोज लगाना।
- बबल सॉर्ट को एक चक्कर के बाद रोक देना। तब तक दोहराओ जब तक कोई अदला-बदली न हो।
- मान लेना कि द्विआधारी खोज हमेशा बेहतर है: छोटी या बिना छँटी सूची में रेखीय खोज आसान और जल्दी हो सकती है।
- मर्ज सॉर्ट में दोनों हिस्सों को बिना तुलना किए एक के बाद एक जोड़ देना।