Algorithms and Programming | AP

Repeatedly find the minimum element from the unsorted portion and place it at the beginning.

Java implementation:

public static void selectionSort(int[] arr) {
    int n = arr.length;
    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;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

AP CSP Pseudocode:

PROCEDURE selectionSort(list)
{
    FOR i <- 1 TO LENGTH(list)
    {
        minIdx <- i
        FOR j <- i + 1 TO LENGTH(list)
        {
            IF (list[j] < list[minIdx])
            {
                minIdx <- j
            }
        }
        temp <- list[i]
        list[i] <- list[minIdx]
        list[minIdx] <- temp
    }
}

Intuition. Imagine picking cards from a shuffled deck one at a time. You scan all remaining Cards, find the smallest, and place it next in your sorted hand. After $n$ passes, your hand is Fully sorted.

Why selection sort is $O(n^2)$. The outer loop runs $n-1$ times. For each outer iteration, the Inner loop scans the remaining unsorted portion. The total number of comparisons is $(n-1) + (n-2) + \cdots + 1 = n(n-1)/2 = O(n^2)$.

Stability. Selection sort is not stable because swapping arr[i] with arr[minIdx] can Move an equal element past another equal element.

Worked Example. Trace selection sort on [5, 3, 8, 1, 2].

Pass 1: min = 1 (index 3). Swap arr[0] and arr[3]: [1, 3, 8, 5, 2]. Pass 2: min = 2 (index 4). Swap arr[1] and arr[4]: [1, 2, 8, 5, 3]. Pass 3: min = 3 (index 4). Swap arr[2] and arr[4]: [1, 2, 3, 5, 8]. Pass 4: min = 5 (index 3). Swap arr[3] with itself: [1, 2, 3, 5, 8].

Builds the sorted array one element at a time by inserting each element into its correct position.

Java implementation:

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Intuition. Imagine sorting a hand of playing cards. You hold the first card in your left hand (sorted). You pick up the next card with your right hand and insert it into the correct position in Your left hand by shifting larger cards to the right.

Why insertion sort is $O(n^2)$ in the worst case. If the array is in reverse order, each new Element must be shifted all the way to the front. The $i$-th element requires up to $i$ shifts, so The total is $1 + 2 + \cdots + (n-1) = O(n^2)$.

Best case $O(n)$. If the array is already sorted, each element requires zero shifts.

A divide-and-conquer algorithm that recursively splits the array, sorts each half, and merges them.

Java implementation:

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < temp.length; p++) {
        arr[left + p] = temp[p];
    }
}

Complexity analysis. The recursion tree has $\log_2 n$ levels. At each level, a total of $n$ Elements are merged.

$T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$

This holds for best, average, and worst case.

When to use each. Insertion sort is best for small or nearly sorted arrays. Merge sort is Reliable for large datasets. Quick sort is often faster in practice but has an $O(n^2)$ worst case.

Checks each element sequentially until the target is found or the list ends.

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Works on unsorted and sorted lists. Worst case: $O(n)$ comparisons.

Works on sorted arrays by repeatedly dividing the search interval in half.

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Requires the array to be sorted. Worst case: $O(\log n)$ comparisons.

Loop invariant: If target exists in arrThen arr[low] <= target <= arr[high] at the start Of each iteration.

Initialization: Before the first iteration, low = 0 and high = n - 1So the invariant Holds.

Maintenance: If arr[mid] < targetWe set low = mid + 1. Since the array is sorted and arr[mid] < target``target must be in arr[mid+1..high]. Similarly for the other case.

Termination: The loop terminates when low > highMeaning the search space is empty. Since the Invariant guarantees the target would be in [low, high] if it existed, the target is not in the Array.

$\blacksquare$

Big-O notation describes the upper bound of an algorithm”s time or space complexity.

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \le c \cdot g(n)$ For all $n \ge n_0$.

Rule 1: Sequential statements: add complexities. $O(a) + O(b) = O(\max(a, b))$.

Rule 2: Nested loops: multiply complexities. $O(a) \times O(b) = O(a \cdot b)$.

Rule 3: Drop constants and lower-order terms. $O(3n^2 + 5n + 100) = O(n^2)$.

• Computational Thinking — Algorithm design applies the decomposition and pattern recognition principles of computational thinking.
• Computing Systems — Hardware architecture and memory models influence how algorithms are implemented and optimised.
• Data Analysis — Algorithms for sorting and searching are applied to data sets analysed using statistical methods.