Sorting and Searching

Introduction

Sorting arranges records in a specified order (ascending or descending). Searching locates an element within a data set. Both are fundamental and studied together because many search algorithms assume sorted input.

Bubble Sort

Compare adjacent elements and swap if out of order. After each pass, the largest element "bubbles" to the end.

for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - i - 1; j++)
        if (a[j] > a[j+1]) swap(&a[j], &a[j+1]);

Time: O(n²). Space: O(1). Stable.

Selection Sort

Find the minimum of the unsorted part and swap it with the first unsorted position.

for (i = 0; i < n - 1; i++) {
    int m = i;
    for (j = i + 1; j < n; j++) if (a[j] < a[m]) m = j;
    swap(&a[i], &a[m]);
}

Time: O(n²). Space: O(1). Not stable.

Insertion Sort

Insert each new element into the sorted left portion. Efficient for small or nearly sorted arrays.

for (i = 1; i < n; i++) {
    int k = a[i], j = i - 1;
    while (j >= 0 && a[j] > k) { a[j+1] = a[j]; j--; }
    a[j+1] = k;
}

Time: O(n²) worst, O(n) best. Stable.

Merge Sort

Divide and conquer: split the array in half, sort each half recursively, then merge.

Time: O(n log n) guaranteed. Space: O(n) auxiliary. Stable.

Quick Sort

Pick a pivot, partition the array so that elements < pivot go left and > pivot go right, then recurse.

Time: O(n log n) average, O(n²) worst (rare with randomized pivot). Space: O(log n) stack. Not stable.

Heap Sort

Build a max-heap in O(n), then repeatedly extract the max and place it at the end. Time: O(n log n). Space: O(1). Not stable.

Comparison Table

Linear Search

Scan every element until the target is found. O(n). Works on any list.

Binary Search

Requires a sorted array. Repeatedly halve the search range. O(log n) time, O(1) iterative space.

int bsearch(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2;
        if (a[m] == key) return m;
        if (a[m] < key) lo = m + 1; else hi = m - 1;
    }
    return -1;
}

Summary

Choose the algorithm to match the data: insertion sort for small or mostly-sorted arrays, quicksort for general-purpose in-memory sorts, mergesort when stability is required, heapsort when O(1) extra space is required. Use binary search whenever data is sorted.

Important Questions

1. Explain bubble sort with an example and analyze complexity.
2. Write the algorithm for selection sort and insertion sort.
3. Explain merge sort and its time complexity.
4. Explain quick sort and show one partitioning step.
5. Compare all sorting algorithms in a table.
6. Define stable vs unstable sort and give one example of each.
7. Write the binary search algorithm and prove its O(log n) time.
8. Differentiate linear and binary search.