Theory
Principal को toppers की list चाहिए
Marks array में {55, 90, 62, 78, 70} है। Program पर दो request आती हैं:
1. "किसी के ठीक 62 हैं? कौन सी position?" (search)
2. "Marks सबसे कम से सबसे ज़्यादा तक print कीजिए।" (sort)
इंसान दोनों सहज-बोध से करते हैं। Program को एक recipe चाहिए: सटीक steps जिन्हें एक loop follow कर सके। आज: एक search recipe और दो sort recipes, मिलाकर इस पूरे subject के सबसे पक्के exam सवाल।
Theory
Cricket team को height से sort करने के दो तरीके
Bubble sort पड़ोसियों का swap है: players 1-2 की तुलना करो, गलत हो तो swap; फिर 2-3, swap; कतार भर। एक पूरे pass के बाद, सबसे लंबा आदमी अंत तक bubble हो चुका होता है, गारंटीड। बाकी के लिए दोहराओ। Selection sort coach का तरीका है: सबको scan करो, सबसे छोटे को चुनो, उसे पहले रखो; बाकी को scan करो, अगले सबसे छोटे को चुनो, उसे दूसरे रखो। नतीजा वही, मिज़ाज अलग: bubble लगातार swap करता है, selection हर round में एक बार।
Theory
Linear search: बस चलो
62 ढूँढ रहे हैं? Coach पर चलो, berth-दर-berth:
for (i = 0; i < n; i++) {
if (marks[i] == target) {
printf("Found at index %d\n", i);
break; /* why keep looking? */
}
}
तुलना करो, आगे बढ़ो, कामयाबी पर break (पिछला lesson अपनी कमाई करता)। Data के किसी भी क्रम पर काम करता है, यही इसका गुण है; ज़्यादा से ज़्यादा सभी n elements को छूना इसकी कीमत है।
Follow along
Bubble sort, recipe
- अगल-बगल के पड़ोसी a[j] और a[j+1] की तुलना करो अगर बायाँ बड़ा है, तो उन्हें swap करो। सिर्फ पड़ोसी, कभी दूर की जोड़ियाँ नहीं।
- array पर एक पूरा pass खत्म करो सबसे बड़ी value अब आख़िरी position तक bubble हो चुकी, गारंटीड और अंतिम।
- सिकुड़ते unsorted हिस्से पर pass दोहराओ हर pass एक position पहले रुक सकता है: pass i में j < n-1-i।
- n-1 passes के बाद, array sorted है Swapping को एक temp box चाहिए: t = a; a = b; b = t।
Practical
Bubble sort C में
#include <stdio.h>
int main() {
int marks[5] = {55, 90, 62, 78, 70};
int i, j, temp, n = 5;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (marks[j] > marks[j + 1]) {
temp = marks[j];
marks[j] = marks[j + 1];
marks[j + 1] = temp;
}
}
}
for (i = 0; i < n; i++) printf("%d ", marks[i]);
return 0;
}This example runs in Gri-Learn on the web, where you can edit it and see the output.
Think first
Pass one trace कीजिए
{55, 90, 62, 78, 70} लीजिए और कागज़ पर एक bubble pass चलाइए: positions 0-1, 1-2, 2-3, 3-4 की तुलना कीजिए, जहाँ बायाँ बड़ा हो वहाँ swap करते हुए। Pass के बाद array कैसा दिखता है?
Show the answer
55-90: ठीक। 90-62: swap → {55, 62, 90, 78, 70}। 90-78: swap → {55, 62, 78, 90, 70}। 90-70: swap → {55, 62, 78, 70, 90}।
एक pass के बाद: {55, 62, 78, 70, 90}। अभी sorted नहीं, पर 90, सबसे बड़ी, अपनी अंतिम सीट पर पहुँच गई। वह one-pass trace, ठीक ऐसे ही लिखा, एक स्थायी exam सवाल है।
Quiz
किसी भी array पर bubble sort के पहले पूरे pass के बाद, क्या गारंटीड है?
- सबसे बड़ा element आख़िरी position में है
- पूरा array पूरी तरह sorted है
- सबसे छोटा element पहली position में है
- सारे passes खत्म होने तक कुछ भी गारंटीड नहीं
Show the answer
सबसे बड़ा element आख़िरी position में है
हर तुलना बड़े पड़ोसी को दाईं तरफ धकेलती है, इसलिए pass अधिकतम को बिलकुल अंत तक बहा ले जाता है, उसका अंतिम घर। सबसे छोटे का आगे पहुँचना SELECTION sort के pass-one का वादा है (जब minimums चुने जाते हैं), दोनों गारंटियाँ एक क्लासिक exam confusion जोड़ी हैं।
Quiz
marks[j] और marks[j+1] को swap करने के लिए, एक student लिखता है: marks[j] = marks[j+1]; marks[j+1] = marks[j]; असल में क्या होता है?
- दोनों boxes आख़िर में एक ही value रखते हैं; मूल marks[j] खो जाता है
- Values सही swap होती हैं
- एक compile error: swapping के लिए function चाहिए
- Array खाली हो जाता है
Show the answer
दोनों boxes आख़िर में एक ही value रखते हैं; मूल marks[j] खो जाता है
पहला assignment marks[j] को OVERWRITE कर देता है, किसी के सहेजने से पहले उसकी पुरानी value मिटाकर; फिर दूसरा वही value वापस copy करता है। नतीजा: duplicates, कोई swap नहीं। इलाज temp variable है: temp = marks[j]; marks[j] = marks[j+1]; marks[j+1] = temp। खोई-value वाला swap सबसे पसंदीदा spot-the-bug सवालों में है।
Watch out
Marks कहाँ कटते हैं
बिना temp swap करना (ऊपर वाला quiz)। गलत inner bound: j को n-1-i पर रुकना चाहिए; j को n-1 तक चलाइए और आख़िरी compare पर marks[j+1] out of bounds चला जाता है। दोनों sorts को तुलना में मिलाना: bubble हर pass में कई बार अगल-बगल पड़ोसियों को swap करता है; selection minimum के लिए scan करता है और हर pass में ज़्यादा से ज़्यादा एक swap करता है। वह फ़र्क़ बताइए और compare-the-sorts वाला सवाल आपका है।
Theory
आप अभी algorithms से मिले
इन recipes का एक भव्य नाम है, algorithms, और BCA304 एक पूरा subject इन्हें देता है (जहाँ आप यह भी सीखेंगे कि बड़े data के लिए bubble sort क्यों धीमा है, और binary search से मिलेंगे, जो sorted array में items बेतुकी तेज़ी से ढूँढता है)। अभी के लिए: marks program किसी भी student को ढूँढ सकता है और merit list print कर सकता है। आगे: grid, students × subjects, two-dimensional arrays।
Summary
Key takeaways
- Linear search: 0 से n-1 तक चलो, तुलना करो, मिलने पर break; unsorted पर काम करता है।
- Bubble sort: out-of-order अगल-बगल जोड़ियों को swap करो; हर pass max को अंत तक bubble करता है।
- Inner bubble loop: j < n-1-i; n-1 passes, n elements को sort करते हैं।
- Swap को temp चाहिए: t = a; a = b; b = t (इसके बिना, एक value खो जाती है)।
- Selection sort: minimum ढूँढो, हर pass में एक swap से आगे रखो।
- याद रखने का hook: bubbles ऊपर उठते हैं, सबसे बड़ा पहले top (अंत) तक पहुँचता है।