एक-एक करके जांच करना
रैखिक खोज: एक-एक करके जांच करें
कल्पना करें कि आपके पास 10 कार्ड हैं जो उल्टे हुए हैं, 1 से 10 तक नंबर दिए गए हैं, यादृच्छिक क्रम में फेरे हुए हैं।
आप संख्या 7 वाला कार्ड खोजना चाहते हैं।
आप एक-एक करके कार्ड पलटते हैं, बाएं से दाएं, जब तक आप इसे नहीं ढूंढते।
| परिस्थिति | फ्लिप की संख्या |
|---|---|
| सर्वश्रेष्ठ स्थिति | 1 फ्लिप (भाग्यशाली पहली कोशिश!) |
| सबसे खराब स्थिति | 10 फ्लिप (यह आखिरी कार्ड था) |
| औसत | लगभग 5 फ्लिप |
अब 100 कार्डों की कल्पना करें। औसत: लगभग 50 फ्लिप।
1,000 कार्ड? औसत: लगभग 500 फ्लिप।
पैटर्न देखें? कार्ड दोगुने, काम दोगुना। काम एक सीधी रेखा में बढ़ता है।
कंप्यूटर वैज्ञानिक इसे रैखिक खोज कहते हैं — रैखिक का मतलब है कि काम एक रेखा की तरह बढ़ता है: स्थिर & अनुमानित।
रैखिक खोज किसी भी सूची पर काम करती है, सॉर्ट की गई हो या नहीं। यह इसे सरल बनाता है। लेकिन यह धीमा हो सकता है।
कितने नाम?
आपके पास 20 नामों की कक्षा सूची है जो यादृच्छिक क्रम में लिखी है।
आप नाम Zoe खोजने के लिए हैं।
आप एक-एक नाम की जांच करते हैं, सूची के शीर्ष से नीचे तक।
सूची को आधा काटें
बाइनरी खोज: बीच में कूदें
बाइनरी खोज का एक नियम है: सूची पहले सॉर्ट की जानी चाहिए।
यदि आपकी 20 नामों की सूची A से Z तक जाती है, तो आप बाइनरी खोज का उपयोग कर सकते हैं।
यह कैसे काम करता है: बीच के नाम (नाम #10) पर खोलें। पूछें: क्या Zoe इस नाम से पहले है या बाद में?
Z वर्णमाला के अंत के पास आता है, इसलिए Zoe बीच के बाद आता है। पहली आधी सूची को हटा दें। अब आपके पास केवल नाम 11-20 बचे हैं।
उन 10 नामों के बीच की जांच करें (नाम #15)। Z M के बाद आता है, इसलिए Zoe नाम #15 के बाद आता है। नाम 11-14 को हटा दें। अब आपके पास नाम 16-20 हैं।
आधा करते रहें। प्रत्येक जांच शेष आधे नामों को हटाती है।
| सूची का आकार | बाइनरी खोज के साथ अधिकतम जांच |
|---|---|
| 20 नाम | अधिकतम 5 जांच |
| 1,000 नाम | अधिकतम 10 जांच |
| 1,000,000 नाम | अधिकतम 20 जांच |
इसकी तुलना 1,000,000 नामों पर रैखिक खोज से करें: औसतन 500,000 जांच।
बाइनरी खोज हर बार सूची को आधा काटती है। बार-बार आधा करना बहुत जल्दी 1 तक पहुंचता है — यही वजह है कि यह इतना तेज़ रहता है।
एक सॉर्ट की गई सूची में 'fig' खोजें
यहाँ 8 शब्दों की एक सॉर्ट की गई सूची है:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
आप fig को बाइनरी खोज का उपयोग करके खोजना चाहते हैं।
याद रखें: बीच की जांच करें, पूछें कि क्या आपका लक्ष्य पहले या बाद में आता है, फिर सूची को आधा काटें।
पड़ोसियों को क्रम में स्वैप करना
बबल सॉर्ट: पड़ोसियों की तुलना करें & स्वैप करें
बबल सॉर्ट एक बार में दो पड़ोसी आइटमों की तुलना करके सूची को क्रम में रखता है।
यदि दो पड़ोसी क्रम से बाहर हैं — उन्हें स्वैप करें।
सूची के माध्यम से पास बनाते रहें जब तक कि कोई स्वैप करने की आवश्यकता न हो।
उदाहरण: [5, 3, 8, 1] को सॉर्ट करें
पास 1:
- 5 & 3 की तुलना करें। 5 > 3, तो स्वैप करें → [3, 5, 8, 1]
- 5 & 8 की तुलना करें। 5 < 8, कोई स्वैप नहीं → [3, 5, 8, 1]
- 8 & 1 की तुलना करें। 8 > 1, तो स्वैप करें → [3, 5, 1, 8]
पास 2:
- 3 & 5 की तुलना करें। ठीक है → [3, 5, 1, 8]
- 5 & 1 की तुलना करें। 5 > 1, स्वैप करें → [3, 1, 5, 8]
- 5 & 8 की तुलना करें। ठीक है → [3, 1, 5, 8]
पास 3:
- 3 & 1 की तुलना करें। 3 > 1, स्वैप करें → [1, 3, 5, 8]
- 3 & 5 की तुलना करें। ठीक है। 5 & 8 की तुलना करें। ठीक है।
हो गया! [1, 3, 5, 8] ✓
ध्यान दें: सबसे बड़ी संख्या प्रत्येक पास पर सूची के अंत तक बुलबुले की तरह जाती है। यही बबल सॉर्ट को इसका नाम देता है।
बबल सॉर्ट काम करता है। यह बड़ी सूचियों के लिए सबसे तेज़ नहीं है, लेकिन यह समझने में आसान है — सीखने के लिए परफेक्ट।
बबल सॉर्ट के साथ [4, 2, 7, 1] को सॉर्ट करें
बबल सॉर्ट का उपयोग करके इस सूची को सॉर्ट करें: [4, 2, 7, 1]
प्रत्येक पास के बाद सूची दिखाएँ। गिनें कि खत्म करने में कितने पास लगते हैं।