Searching and Sorting Algorithms

# CHAPTER 24

Searching and Sorting Algorithms #

1. Introduction #

2. Learning Objectives #

• Implement Linear Search and Binary Search.

• Understand Time Complexity (Big-O Notation) basics.

• Implement Bubble Sort, Selection Sort, and Insertion Sort.

• Decide which algorithm to use based on the dataset.

3. Linear Search #

• Time Complexity: O(n) (Worst case: element is at the end, requires n checks).

• Requirement: Works on unsorted arrays.

#include <stdio.h>

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Found! Return index
        }
    }
    return -1; // Not found
}

int main() {
    int arr[] = {10, 50, 30, 70, 80, 60, 20, 90, 40};
    int index = linearSearch(arr, 9, 30);
    printf("Found at index: %d\n", index);
    return 0;
}

4. Binary Search #

• Time Complexity: O(log n) (Extremely fast. Searching 1,000,000 items takes at most 20 checks).

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

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

        if (arr[mid] == target) return mid;       // Found
        if (arr[mid] < target) low = mid + 1;     // Ignore left half
        else high = mid - 1;                      // Ignore right half
    }
    return -1; // Not found
}

5. Bubble Sort #

• Time Complexity: O(n²) (Very slow for large datasets).

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // Last i elements are already sorted
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

6. Selection Sort #

• Time Complexity: O(n²).

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; // Found a new minimum
            }
        }
        // Swap
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

7. Insertion Sort #

• Time Complexity: O(n²). Very fast if the array is *almost* sorted (O(n)).

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

8. Common Mistakes #

• Using Binary Search on Unsorted Data: Binary Search logic fundamentally relies on order. If the data is unsorted, it will return -1 incorrectly.

• Bubble Sort j loop limit: The inner loop should go to size - i - 1. If it goes to size - 1, it will check arr[j+1] which might be out of bounds!

• Swapping logic: A proper swap requires a temporary variable (temp). Doing a = b; b = a; makes them both identical.

9. Exercises #

1. 1. Modify Bubble Sort to include a boolean swapped flag. If a full pass happens without any swaps, break the loop early (Optimized Bubble Sort).

1. 2. Trace Insertion Sort on paper for the array: {12, 11, 13, 5, 6}.

10. MCQ Quiz with Answers #

11. Interview Questions #

• Q: Explain why Binary Search is O(log n) time complexity.

• Q: When would Insertion Sort be a better choice than Bubble Sort or Selection Sort?

• Q: Explain the swapping bug a = b; b = a; and how to fix it using a temporary variable or XOR bitwise logic.

12. Summary #

13. Next Chapter Recommendation #