05. Elementary Sorting

Shared Setting and Invariants#

We sort an integer array in ascending order. The C routines take inclusive indices lo and hi; call them on a full nonempty array as sort(a,0,n-1). An empty range uses hi < lo and performs no accesses. A loop invariant is a fact true before and after each iteration. It explains how local steps accumulate a correct answer rather than merely describing what happens.

All three elementary sorts use constant auxiliary space. Their worst-case time is quadratic, but they differ in comparisons, movements, stability and adaptation. Those differences are meaningful for small or nearly ordered inputs.

Selection Sort: Choose the Next Minimum#

At position i, scan the remaining suffix for its smallest value and swap that value into i. Before iteration i, positions before i contain the smallest items in sorted order. Finding the smallest remaining item extends that prefix by one. Stop after placing the second-last item; the final one is already determined.

void selectionSort(int a[], int lo, int hi) {
    for (int i = lo; i < hi; i++) {
        int min = i;
        for (int j = i + 1; j <= hi; j++) {
            if (a[j] < a[min]) min = j;
        }
        swap(a, i, min);
    }
}

swap is the helper in Searching and Sorting. min stores an index, not the smallest value; otherwise the final swap would not know which position to exchange.

For original example [4,3,1,2]:

Watch the selected minimum change during the suffix scan; it is placed only after the whole suffix has been inspected.

Comparisons and Stability#

For n items, suffix comparisons number (n-1)+(n-2)+...+1 = n(n-1)/2. Already sorted input cannot avoid those scans, so best, average and worst time are all quadratic. There are n-1 swap calls, some exchanging a position with itself. It can therefore be attractive when writes are expensive compared with comparisons.

The lecture's duplicate example reveals instability. Label the two sixes to make the order visible:

[6_A,6_B,5,2] becomes [2,6_B,5,6_A], then [2,5,6_B,6_A]. The final equal-key order has reversed. Strictly choosing the first minimum does not rescue stability: the displaced item can jump over an equal item during the swap.

Practice. How many key comparisons does selection sort perform on six already sorted values? Could skipping self-swaps change the time class?

Modified Bubble Sort: Settle the Maximum#

Compare adjacent entries from left to right; exchange a pair only if the left one is larger. The maximum of the current unsorted range travels to its right end. The next pass excludes that settled entry. The lecture uses an early-exit flag: a pass with no exchanges proves the whole active range is already ordered. A traditional version that always completes every scheduled pass remains quadratic even on sorted input; the flag is what gives this modified version its linear best case.

#include <stdbool.h>

void bubbleSort(int a[], int lo, int hi) {
    for (int end = hi; end > lo; end--) {
        bool swapped = false;
        for (int j = lo; j < end; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

During one pass, after comparing pair j,j+1, position j+1 holds the maximum seen so far in that pass. At the final pair, this is the maximum of the whole active prefix. The outer invariant is that the excluded suffix is sorted and at least as large as every remaining entry.

Read each row as the state after the highlighted pair is considered. On [4,3,6,1,2,5], swap 4,3, leave 4,6, then exchange 6 with 1, 2, and 5. The first pass finishes [3,4,1,2,5,6]. The next pass settles 5, and the third settles 4, leaving [1,2,3,4,5,6].

A further pass still matters: the algorithm does not magically know the array is sorted just because we can see it. The no-swap pass supplies that evidence. Watch the final confirming pass:

Cost and Equal Keys#

On already sorted input, one pass makes n-1 comparisons and exits: linear time. On reverse input, every adjacent comparison swaps a pair and all shrinking passes are required, giving n(n-1)/2 comparisons and swaps: quadratic time. The slide analysis has a repeated n-1 label for the second pass; the actual code reduces the active end, so that pass has n-2 comparisons.

For uniformly random permutations of distinct keys, each pair is equally likely to be inverted. An inversion is a pair whose earlier element is larger than its later element. There are n(n-1)/2 pairs, half inverted on average, so expected inversions are n(n-1)/4. An adjacent out-of-order swap removes exactly one inversion. Thus expected swaps are quadratic, establishing quadratic expected time under this model.

Equal adjacent keys never swap because the condition is strict >. Equal items can change relative order only by crossing, and they cannot cross under that rule; bubble sort is stable. It is adaptive because the no-swap exit exploits order, although one badly positioned small entry can still require many passes.

Practice. What happens on [2_A,2_B,1]? Would changing > to >= preserve stability?

Insertion Sort: Extend a Sorted Prefix#

Treat the first item as a sorted one-item prefix. Take the next item, hold it outside the array conceptually, shift larger preceding items right, and place the held value into the resulting gap. Before iteration i, entries lo..i-1 are sorted. After insertion, lo..i are sorted and contain the same items as before the iteration.

void insertionSort(int a[], int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int item = a[i];
        int j = i;
        while (j > lo && item < a[j - 1]) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = item;
    }
}

The bounds check comes first in the &&: C short-circuit evaluation avoids accessing a[j-1] when the gap reaches lo. Saving item is essential because shifting into a[i] overwrites its original value.

For the lecture example [4,1,7,3,8,6,5,2], inserting 1 shifts 4; inserting 7 shifts nothing; inserting 3 shifts 7 then 4, leaving [1,3,4,7,8,6,5,2].

The slide uses adjacent swaps to display movement, while its implementation uses a held value and shifts. Both produce the same order after each insertion, but a shift trace can temporarily show repeated stored integers. One copy is the value being held, not an additional logical item.

Watch the player lift the held item and track the gap. Its implementation matches the shift-based C above.

The last 2 shifts 8,7,6,5,4,3 and stops after 1. It requires six shifts. That is useful evidence about disorder: “one remaining item” does not mean constant work.

Derive the Adaptive Bound#

If input is sorted, every next item fails its first movement comparison: n-1 comparisons, no shifts, linear time. If reversed, the item at position i moves past all i predecessors, giving 1+2+...+(n-1) shifts and quadratic time. Under uniformly random distinct permutations, expected inversions are quadratic, so expected time is quadratic too.

More precisely, shifting larger predecessors removes one inversion per shift, so running time is Θ(n+I) where I is the number of input inversions. The n term includes considering each next item even when I=0. This explains why insertion sort is particularly good for nearly sorted arrays. Equal predecessors are not shifted by the strict comparison, so ties retain their relative order.

Practice. In [1,2,3,4,0], how many shifts insert the final item? Is “mostly sorted” a sufficient performance description?

Practice. Why might insertion beat bubble sort although both have linear best-case and quadratic average/worst-case bounds?

Choose With the Mechanism in Mind#

All three have constant auxiliary space for arrays. For large arbitrary data, merge sort and quicksort usually improve growth. For a tiny or nearly sorted range, insertion sort's simple loop can still be a sensible component of a faster hybrid.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Trace one full left-to-right bubble-sort pass on [4,1,3,2]. What invariant holds afterward?

Question 2. Count the shifts insertion sort makes on [5,4,3,2,1]. How does that support its worst-case bound?

Question 3. Modified bubble sort resets a swapped flag before each pass and stops after a pass with no swaps. How many comparisons does it make on an already sorted length-n array, and why is that not Θ(1)?