Elementary Sorting: Bubble, Selection and Insertion

• Time and Space Complexity Analysis: counting nested loops, best and worst case.
• Arrays with 1-based indexing, as in the pseudocode below.

Properties used to classify sorts

• In place. uses $O(1)$ auxiliary memory besides the input array.
• Stable. records with equal keys keep their original relative order. Stability matters when sorting by one key after another (sort by name, then stably by city, and names stay sorted within each city).
• Adaptive. runs faster on input that is already nearly sorted.
• Online. can sort the input as it arrives, one element at a time.
• Comparison-based. examines keys only by comparing pairs. All three sorts here are comparison-based, so the $\Omega(n \lg n)$ lower bound of Comparison of Sorting Algorithms applies to them.

Inversions

• $I = 0$ exactly when the array is sorted.
• $I = n(n-1)/2$, the maximum, exactly when the array is in strictly decreasing order.
• Averaged over all $n!$ orderings of distinct keys, $I = n(n-1)/4$: each of the $\binom{n}{2}$ pairs is inverted in exactly half of the orderings.
• Swapping unequal adjacent keys changes $I$ by exactly 1; swapping equal keys leaves $I$ unchanged. So any sort that only exchanges adjacent elements (bubble sort, insertion sort) performs at least $I$ exchanges, and is $\Omega(n^2)$ on average.

SELECTION-SORT(A, n)
    for i <- 1 to n - 1
        min <- i
        for j <- i + 1 to n
            if A[j] < A[min] then min <- j
        if min != i then exchange A[i] with A[min]

• Comparisons are always $\sum_{i=1}^{n-1}(n - i) = n(n-1)/2$, whatever the input. Time is $\Theta(n^2)$ in the best, worst and average cases: selection sort is not adaptive.
• Exchanges: at most $n - 1$, the fewest of the three methods. This makes selection sort a reasonable choice when writing an element is much more expensive than comparing.
• In place.
• Not stable in the array form above. Example with keys compared by number only: $2_a, 2_b, 1$. At $i = 1$ the minimum 1 is exchanged with $2_a$, giving $1, 2_b, 2_a$; the two 2s have changed order. A stable variant inserts the minimum by shifting instead of exchanging, at the cost of $\Theta(n^2)$ moves.

BUBBLE-SORT(A, n)
    for pass <- 1 to n - 1
        swapped <- FALSE
        for i <- 1 to n - pass
            if A[i] > A[i + 1]
                exchange A[i] with A[i + 1]
                swapped <- TRUE
        if swapped = FALSE then return

• Exchanges equal $I$ (each adjacent exchange removes one inversion).
• Passes. An element moves left by at most one position per pass. So the number of passes that make an exchange equals the largest number of greater elements to the left of any element. Here element 1 has four greater elements before it, so passes 1 to 4 exchange, and pass 5 confirms.
• With the swapped flag: best case (sorted input) is one pass of $n - 1$ comparisons, $\Theta(n)$. Without the flag, bubble sort always makes $n(n-1)/2$ comparisons.
• Worst case (decreasing input): $n(n-1)/2$ comparisons and exchanges, $\Theta(n^2)$. Average $\Theta(n^2)$.
• In place and stable (only strictly greater neighbours are exchanged).

• Insertion sort comparisons, exactly. The stopping comparison is missing only when the key becomes the new minimum, that is when $A[j]$ is smaller than everything before it (a prefix minimum, $j \ge 2$). So comparisons $= I + (n - 1) - m$, where $m$ is the number of prefix minima at positions 2 to $n$. In the trace, 2 and 1 are prefix minima: $9 + 5 - 2 = 12$. On decreasing input every key is a prefix minimum, giving $n(n-1)/2 + (n-1) - (n-1) = n(n-1)/2$.
• Selection sort on decreasing input makes only $\lfloor n/2 \rfloor$ exchanges, not $n - 1$. For 6 5 4 3 2 1: $i = 1$ gives 1 5 4 3 2 6, $i = 2$ gives 1 2 4 3 5 6, $i = 3$ gives 1 2 3 4 5 6, and $i = 4, 5$ find the minimum already in place. Each exchange fixes two positions, the outer pair.
• Bubble sort passes, turtle against rabbit. With the flag, 2 3 4 5 6 1 takes 5 passes (the 1 moves one place per pass), while 6 1 2 3 4 5 takes 2 passes (the 6 reaches the end in pass 1, and pass 2 confirms). Both arrays have $I = 5$, so the exchange counts agree while the pass counts differ.

• $n = 0$ or $n = 1$: all three loops do nothing useful and terminate; the array is trivially sorted.
• All keys equal: $I = 0$. Insertion sort and flagged bubble sort take $\Theta(n)$; selection sort still takes $\Theta(n^2)$ comparisons and makes no exchange (with the min != i test).
• Changing > to >= in insertion sort or bubble sort destroys stability and adds useless moves of equal keys.
• An array of distinct keys that becomes sorted when one element is moved $d$ positions has exactly $d$ inversions, so insertion sort sorts it in $\Theta(n + d)$ time.

• Any algorithm that exchanges only adjacent elements needs at least $I$ exchanges, so it is $\Omega(n^2)$ in the worst and average cases. Breaking the quadratic barrier requires moving elements over long distances (Shell sort, merge sort, quicksort, heapsort).
• Insertion sort is the method of choice for small $n$ and nearly sorted input; hybrid sorts switch to it below a small cut-off.
• Selection sort minimises writes; insertion sort minimises comparisons on nearly sorted data.
• After $k$ passes, bubble sort has placed the $k$ largest elements and selection sort the $k$ smallest; insertion sort has sorted the first $k + 1$ elements (which need not be the smallest).

• State after $k$ passes. Be precise about what each algorithm guarantees (largest at the end for bubble, smallest at the front for selection, sorted prefix of original elements for insertion).
• Counting. swaps of bubble sort and shifts of insertion sort equal the number of inversions; selection sort's comparisons are always $n(n-1)/2$.
• Stability and in-place questions. bubble and insertion are stable; array selection sort is not; all three are in place.
• Best case traps. bubble sort is $\Theta(n)$ only with the early-exit flag; selection sort is never better than $\Theta(n^2)$.
• Exact-count traps. insertion sort comparisons are $I + (n-1) - m$; selection sort on decreasing input exchanges $\lfloor n/2 \rfloor$ times; bubble sort passes depend on how far the smallest elements must travel left, not on $I$.

• Time and Space Complexity Analysis: prerequisite. Nested-loop counting.
• Merge Sort: dependent. A stable $\Theta(n \lg n)$ sort; counting inversions by merging.
• Linear-Time Sorting: dependent. Stable sorting below the comparison bound.
• Comparison of Sorting Algorithms: related. The full comparison table and the $\Omega(n \lg n)$ lower bound.
• Searching: related. Binary search inside binary insertion sort.