Sorting and Searching

🔍 Sorting & Searching: The Great Library Adventure

Imagine you’re a librarian in a magical library with millions of books. How do you find the one book someone needs? And how do you keep them organized so finding is easy?

🎯 The Big Picture

Think of sorting like arranging your toys by size - smallest to biggest. And searching is like finding your favorite toy in that organized pile.

Why do we care?

• Finding things FAST saves time
• Organized data = Happy computers
• Every app you use does this millions of times!

📚 Part 1: SORTING ALGORITHMS

“Before you can find anything fast, you need to put things in order!”

What is Sorting?

Imagine you have 5 playing cards: 7, 2, 9, 4, 1

Sorting means arranging them: 1, 2, 4, 7, 9 ✨

🫧 Bubble Sort - The Friendly Swap

The Story: Imagine bubbles rising in water. The biggest bubbles float to the top first!

How it works:

1. Look at two neighbors
2. If left is bigger than right, SWAP them
3. Keep doing this until no swaps needed

Real Life Example: Kids lining up by height. The tallest keeps moving to the back!

void bubbleSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                // Swap neighbors
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Example Walk-through:

[5, 3, 8, 1] → Compare 5,3 → Swap!
[3, 5, 8, 1] → Compare 5,8 → OK
[3, 5, 8, 1] → Compare 8,1 → Swap!
[3, 5, 1, 8] → 8 is now in place! 🎉
... keep going until done

Speed: Slow for big lists (like checking every single book!)

🔘 Selection Sort - The Picker

The Story: Imagine picking the smallest candy from a jar, one at a time, and putting them in a new row.

How it works:

1. Find the SMALLEST item
2. Put it in the first spot
3. Find the next smallest
4. Repeat!

void selectionSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {
        int minIdx = i;
        for(int j = i+1; j < n; j++) {
            if(arr[j] < arr[minIdx])
                minIdx = j;
        }
        // Swap smallest to front
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Example:

[64, 25, 12, 22]
Find smallest: 12 → Swap with 64
[12, 25, 64, 22]
Find smallest in rest: 22 → Swap
[12, 22, 64, 25]
... and so on!

📥 Insertion Sort - The Card Player

The Story: Ever sorted playing cards in your hand? You pick up one card and slide it into the right spot among the cards you’ve already sorted!

How it works:

1. Take one item
2. Insert it in the correct position
3. Shift others if needed

void insertionSort(int arr[], int n) {
    for(int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Shift bigger elements right
        while(j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

Example:

Hand: [5] Pick up 2
[2, 5] ← 2 slides before 5
Pick up 8
[2, 5, 8] ← 8 stays at end
Pick up 1
[1, 2, 5, 8] ← 1 slides to front!

Best for: Small lists or almost-sorted data!

⚡ Quick Sort - The Speed Champion

The Story: Imagine sorting a pile of toys by picking ONE toy (the pivot) and making two piles: “smaller than pivot” and “bigger than pivot”. Then do the same for each pile!

How it works:

1. Pick a “pivot” element
2. Put smaller items LEFT, bigger items RIGHT
3. Repeat for each half

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(arr[j] < pivot) {
            i++;
            // Swap
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if(low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Why it’s FAST: Divide and conquer! Each split makes the problem half as big.

🔀 Merge Sort - The Team Player

The Story: Two friends sorting faster than one! Split the work, sort separately, then combine!

How it works:

1. Split list in HALF
2. Sort each half (split more if needed)
3. MERGE the sorted halves together

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Visual:

graph TD
    A["[38, 27, 43, 3]"] --> B["[38, 27]"]
    A --> C["[43, 3]"]
    B --> D["[38]"]
    B --> E["[27]"]
    C --> F["[43]"]
    C --> G["[3]"]
    D --> H["[27, 38]"]
    E --> H
    F --> I["[3, 43]"]
    G --> I
    H --> J["[3, 27, 38, 43]"]
    I --> J

🗑️ Heap Sort - The Priority Expert

The Story: Imagine a special tree where the parent is ALWAYS bigger than children. The biggest item sits at the very top!

How it works:

1. Build a “heap” (special tree structure)
2. Remove the biggest (root)
3. Fix the heap
4. Repeat!

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if(left < n && arr[left] > arr[largest])
        largest = left;
    if(right < n && arr[right] > arr[largest])
        largest = right;

    if(largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Build heap
    for(int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements
    for(int i = n-1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

📊 Sorting Speed Comparison

🔎 Part 2: SEARCHING ALGORITHMS

“Now that things are organized, let’s find what we need!”

📖 Linear Search - The Patient Reader

The Story: Like reading a book page by page until you find the word you want.

How it works:

1. Start at the beginning
2. Check each item one by one
3. Found it? Stop! Not found? Keep going.

int linearSearch(int arr[], int n, int x) {
    for(int i = 0; i < n; i++) {
        if(arr[i] == x)
            return i;  // Found at index i
    }
    return -1;  // Not found
}

Example:

Find 7 in [3, 1, 7, 9, 2]
Check 3? No
Check 1? No
Check 7? YES! Found at index 2 ✅

Best for: Small lists or unsorted data

⚡ Binary Search - The Smart Guesser

The Story: Like guessing a number between 1-100. Someone says “higher” or “lower” and you always guess the MIDDLE. You find it super fast!

IMPORTANT: List must be SORTED first!

How it works:

1. Look at the MIDDLE
2. Too big? Search LEFT half
3. Too small? Search RIGHT half
4. Repeat until found!

int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;

        if(arr[mid] == x)
            return mid;  // Found!

        if(arr[mid] < x)
            left = mid + 1;  // Go right
        else
            right = mid - 1; // Go left
    }
    return -1;  // Not found
}

Example - Find 23:

[2, 5, 8, 12, 16, 23, 38, 56, 72]
        ↑ mid=12
23 > 12 → Search right half

[16, 23, 38, 56, 72]
      ↑ mid=38
23 < 38 → Search left half

[16, 23]
  ↑ mid=16
23 > 16 → Search right

[23] ← FOUND! 🎉

Speed: Super fast! Eliminates HALF the items each step.

🔍 Binary Search (Recursive Version)

Same idea, different style:

int binarySearchRecursive(int arr[],
                          int left,
                          int right,
                          int x) {
    if(right >= left) {
        int mid = left + (right - left) / 2;

        if(arr[mid] == x)
            return mid;

        if(arr[mid] > x)
            return binarySearchRecursive(
                arr, left, mid - 1, x);

        return binarySearchRecursive(
            arr, mid + 1, right, x);
    }
    return -1;
}

🏃 Searching Speed Comparison

What does O(log n) mean?

• 1,000 items → ~10 steps
• 1,000,000 items → ~20 steps
• 1,000,000,000 items → ~30 steps

Binary search is INCREDIBLY fast! 🚀

🎯 When to Use What?

graph TD
    A["Need to Search?"] --> B{Data Sorted?}
    B -->|Yes| C["Binary Search ⚡"]
    B -->|No| D{Worth Sorting?}
    D -->|Yes| E["Sort First → Binary Search"]
    D -->|No| F["Linear Search 🐢"]

Quick Rules:

• Small data (< 10 items): Linear is fine
• Large data, many searches: Sort once, Binary search many times
• One-time search: Linear (sorting takes time too!)

🌟 Key Takeaways

1. Sorting = Organizing data in order
2. Searching = Finding specific data
3. Binary Search needs sorted data but is SUPER fast
4. Quick Sort & Merge Sort are the speed champions
5. Simple sorts (Bubble, Selection, Insertion) are easy to understand but slow

🎮 Real World Examples

Remember: A sorted list is like a organized room - finding things becomes SO much easier! ✨