Operations on one dimensional array (bubble sort, selection sort, linear search)

📖 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

1. અડોઅડ ના પડોશી a[j] અને a[j+1] ને સરખાવો જો ડાબો મોટો હોય, તો એમને swap કરો. ફક્ત પડોશી, ક્યારેય દૂરની જોડી નહીં.
2. array પર એક પૂરો pass પતાવો સૌથી મોટી value હવે છેલ્લી position સુધી bubble થઈ ચૂકી, ગેરંટીડ અને અંતિમ.
3. સંકોચાતા unsorted ભાગ પર pass ફરી કરો દરેક pass એક position વહેલો થોભી શકે: pass i માં j < n-1-i.
4. 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 કેવું દેખાય છે?

🧩 Quiz

કોઈ પણ array પર bubble sort ના પહેલા પૂરા pass પછી, શું ગેરંટીડ છે?

1. સૌથી મોટો element છેલ્લી position માં છે
2. આખું array પૂરી રીતે sorted છે
3. સૌથી નાનો element પહેલી position માં છે
4. બધા passes પતે ત્યાં સુધી કંઈ ગેરંટીડ નથી

🧩 Quiz

marks[j] અને marks[j+1] ને swap કરવા માટે, એક student લખે છે: marks[j] = marks[j+1]; marks[j+1] = marks[j]; ખરેખર શું થાય છે?

1. બંને boxes આખરે એક જ value રાખે છે; મૂળ marks[j] ખોવાઈ જાય છે
2. Values બરાબર swap થાય છે
3. એક compile error: swapping માટે function જોઈએ
4. Array ખાલી થઈ જાય છે

⚠️ 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 થી આગળ મૂકો.
• યાદ રાખવાની યુક્તિ: bubbles ઉપર ઊઠે છે, સૌથી મોટો પહેલા top (અંત) સુધી પહોંચે છે.