Theory
एक pass
नियम: बाएँ से दाएँ चलिए, और जिन 2 पड़ोसियों में बायाँ बड़ा हो, उन्हें swap कीजिए।
{55, 90, 62, 78, 70} पर एक pass चलाइए। अब array कैसा दिखता है?
Think first
पहले आपका pass
एक pass के बाद का array type कीजिए।
Show the answer
{55, 62, 78, 70, 90}। 90, 62, 78 और 70 से आगे swap होता जाता है, इसलिए सबसे बड़ी value आख़िर में पहुँच जाती है: array अभी sorted नहीं है, पर 90 अपनी पक्की जगह पर है।
Theory
Bubble sort
यह bubble sort का एक pass था। हर pass बची हुई सबसे बड़ी value को आख़िर तक ले जाता है, इसलिए n values को sort करने में n-1 passes लगते हैं। 2 boxes को swap करने के लिए एक extra variable चाहिए: temp = a; a = b; b = temp;।
Practical
Bubble sort
#include <stdio.h>
int main() {
int a[5] = {55, 90, 62, 78, 70};
int i, j, temp;
for (i = 0; i < 4; i++)
for (j = 0; j < 4 - i; j++)
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
for (i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}This example runs in Gri-Learn on the web, where you can edit it and see the output.
Quiz
एक student extra variable के बिना swap करता है: a[j] = a[j + 1]; a[j + 1] = a[j];। क्या होता है?
- दोनों boxes में एक ही value रहती है
- दोनों values अपनी जगह ठीक से swap हो जाती हैं
- Compile error
- पूरा array खाली हो जाता है
Show the answer
दोनों boxes में एक ही value रहती है
पहली line a[j] की पुरानी value बचाए बिना उसे बदल देती है, और दूसरी वही value वापस copy कर देती है। इसीलिए swap में temp चाहिए।
Theory
Selection sort और linear search
Selection sort unsorted हिस्से की सबसे छोटी value ढूँढकर उसे उसी हिस्से की शुरुआत में swap करता है: हर pass में ज़्यादा से ज़्यादा एक swap। Linear search index 0 से हर box की तुलना target से करता है, और मिलते ही break से रुक जाता है।
Practical
Linear search
#include <stdio.h>
int main() {
int a[5] = {55, 90, 62, 78, 70};
int i, pos = -1;
for (i = 0; i < 5; i++) {
if (a[i] == 62) {
pos = i;
break;
}
}
if (pos == -1)
printf("Not found");
else
printf("Found at index %d", pos);
return 0;
}This example runs in Gri-Learn on the web, where you can edit it and see the output.
Quiz
ऊपर वाला program क्या print करता है?
- Found at index 2
- Found at index 3
- Not found
- Found at index 2Not found
Show the answer
Found at index 2
62 तीसरी value है, और indexes 0 से शुरू होते हैं, इसलिए pos 2 है। Index 3 तब आता है जब आप 1 से गिनें।
Think first
Exam-style: selection sort
{62, 90, 55, 78, 70} पर selection sort का पहला pass दिखाइए, और bubble sort से एक अंतर बताइए।
Show the answer
{55, 90, 62, 78, 70}: सबसे छोटी value, 55, पहले box से swap होती है। अंतर: selection हर pass में ज़्यादा से ज़्यादा एक swap करता है; bubble पड़ोसियों को कई बार swap करता है।
Summary
Key takeaways
- Bubble sort पड़ोसियों को swap करता है; हर pass सबसे बड़ी value को आख़िर में रखता है।
- Swap के लिए extra variable चाहिए: temp = a; a = b; b = temp;
- Selection sort सबसे छोटी value को आगे लाता है, हर pass में एक swap।
- याद रखने का hook: bubble आख़िर तक उठता है, selection सबसे छोटी चुनता है।