Unit 5 · Lesson 434 minAcademic review pending

Three ways to build sorted order

Compare bubble, selection, and insertion sort through their invariants, movement, and behavior on nearly sorted data.

Choose explanation

After this lesson

You should be able to

Trace all three elementary sorting algorithms.
Select an algorithm based on swaps, stability, and existing order.

Bubble and selection: place an extreme

Bubble sort compares adjacent elements and swaps inverted pairs. After one full ascending pass, the largest remaining value is at the end. An early-exit flag lets it stop when a pass makes no swaps.

Selection sort finds the smallest remaining value and swaps it into the next position. It performs few swaps, but a usual implementation is not stable because one long swap can change the relative order of equal keys.

Selection-sort inner decision

for (size_t start = 0; start + 1 < count; start++) {
    size_t minIndex = start;
    for (size_t i = start + 1; i < count; i++) {
        if (values[i] < values[minIndex]) {
            minIndex = i;
        }
    }
    int temp = values[start];
    values[start] = values[minIndex];
    values[minIndex] = temp;
}

Insertion: grow a sorted prefix

Insertion sort maintains a sorted prefix. Take the next key, shift larger prefix elements right, and insert the key into the gap. It is stable when equal elements are not shifted past each other.

Insertion sort is especially useful for small or nearly sorted data because each key moves only across the inversions before it. All three algorithms can require quadratic work in their ordinary worst cases.

Insertion sort

for (size_t i = 1; i < count; i++) {
    int key = values[i];
    size_t j = i;

    while (j > 0 && values[j - 1] > key) {
        values[j] = values[j - 1];
        j--;
    }
    values[j] = key;
}

Try it yourself

Perform one ascending bubble pass on [5, 1, 4, 2].

Need a hint?

Compare positions (0,1), then (1,2), then (2,3), using the updated array each time.

Check the worked solution

[5,1,4,2] → [1,5,4,2] → [1,4,5,2] → [1,4,2,5]. The largest value reaches the end.

Quick check

Which algorithm naturally maintains a sorted prefix and inserts the next key?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Bubble sort · Insertion sort · Selection sort

Maps to course outcomes CO1, CO3, CO6.