Data Structure: Searching and Sorting (Linear Search, Binary Search, Bubble Sort)

Searching এবং Sorting হলো Data Structure-এর খুব গুরুত্বপূর্ণ অংশ। Searching ব্যবহার করা হয় ডেটা খুঁজে বের করার জন্য এবং Sorting ব্যবহার করা হয় ডেটা সাজানোর জন্য।

---

১. Searching কী?

Searching হলো একটি নির্দিষ্ট ডেটা (value) list বা array-এর মধ্যে খুঁজে বের করার প্রক্রিয়া।

---

২. Linear Search

Linear Search-এ প্রতিটি element একে একে check করা হয়।

উদাহরণ:

Array: [10, 20, 30, 40]
Search: 30
→ 10 (No)
→ 20 (No)
→ 30 (Yes)

Program:

#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40};
    int i, key = 30;

    for(i = 0; i < 4; i++) {
        if(arr[i] == key) {
            printf("Found at index %d", i);
        }
    }

    return 0;
}

Time Complexity: O(n)

---

৩. Binary Search

Binary Search শুধুমাত্র sorted array-এ কাজ করে। এখানে মাঝের element check করা হয়।

উদাহরণ:

Array: [10, 20, 30, 40, 50]
Search: 30
→ Middle = 30 → Found

Program:

#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int low = 0, high = 4, mid, key = 30;

    while(low <= high) {
        mid = (low + high) / 2;

        if(arr[mid] == key) {
            printf("Found at index %d", mid);
            break;
        } else if(arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return 0;
}

Time Complexity: O(log n)

---

৪. Linear vs Binary Search

বিষয়	Linear Search	Binary Search
Data requirement	Sorted না হলেও চলে	Sorted হতে হবে
Speed	Slow	Fast
Complexity	O(n)	O(log n)

---

৫. Sorting কী?

Sorting হলো ডেটাকে একটি নির্দিষ্ট ক্রমে (ascending বা descending) সাজানো।

---

৬. Bubble Sort

Bubble Sort-এ adjacent element compare করে swap করা হয়।

উদাহরণ:

[5, 3, 2]

Step 1: [3, 5, 2]
Step 2: [3, 2, 5]
Step 3: [2, 3, 5]

Program:

#include <stdio.h>

int main() {
    int arr[] = {5, 3, 2};
    int i, j, temp;

    for(i = 0; i < 3-1; i++) {
        for(j = 0; j < 3-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    for(i = 0; i < 3; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Time Complexity: O(n²)

---

৭. Applications

• ✔ Database search
• ✔ Student record sorting
• ✔ Search engines
• ✔ Data analysis

---

৮. বাস্তব জীবনের উদাহরণ

• Linear Search → বই খোঁজা (একটা একটা করে)
• Binary Search → dictionary search
• Sorting → marks list সাজানো

---

উপসংহার

Searching এবং Sorting programming-এর মূল ভিত্তি। Linear এবং Binary Search ডেটা খুঁজতে সাহায্য করে, আর Bubble Sort ডেটা সাজাতে ব্যবহৃত হয়। এগুলো ভালোভাবে বুঝলে advanced algorithm শেখা সহজ হয়।

---

Quick Revision

• Linear → একে একে search
• Binary → middle থেকে search
• Bubble Sort → swap করে sort
• Binary fast, Linear simple