Elementary Sorts — Data Structures Course

What you'll learn

The three elementary sorts — bubble, selection, and insertion — are all O(n²) and rarely the fastest choice. But they're the perfect way to learn sorting: each is a few lines, and watching them side by side builds real intuition for comparisons, swaps, and stability.

By the end you'll be able to:

Trace bubble, selection, and insertion sort step by step
Explain what in-place and stable mean
Know when a simple O(n²) sort is actually the right call

Bubble sort

Repeatedly walk the list comparing neighbors, swapping any that are out of order. Each full pass "bubbles" the largest remaining value to the end. Press play:

Bubble sort

1/29Bubble sort: compare each pair of neighbors and swap them if they are in the wrong order.

Yellow = comparing · purple = swapping · green = settled in final position.

Language

bubble_sort.py

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

Selection sort

Find the smallest value in the unsorted region and swap it into place, growing a sorted region from the left. It always does the same number of comparisons, but the fewest swaps of the three:

Selection sort

1/35Selection sort: repeatedly find the smallest value in the unsorted part and move it to the front.

Scan for the minimum (green), then swap it to the front of the unsorted region.

Language

selection_sort.py

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

Insertion sort

Grow a sorted region on the left; take each new value and slide it back to where it belongs. It's the fastest of the three on nearly-sorted data — almost O(n) then:

Insertion sort

1/20Insertion sort: grow a sorted region on the left, inserting each next value where it belongs.

Each 'key' (purple) shifts larger neighbors right until it drops into place.

Language

insertion_sort.py

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Comparing them

Sort	Best	Average / Worst	Stable?	Notes
`Bubble`	O(n)	O(n²)	Yes	Mostly a teaching tool
`Selection`	O(n²)	O(n²)	No	Fewest swaps (~n)
`Insertion`	O(n)	O(n²)	Yes	Great on small or nearly-sorted data

Note

In-place means it sorts using O(1) extra memory (no second array). Stable means equal elements keep their original relative order — important when sorting records by multiple keys.

Tip

Insertion sort is genuinely useful: libraries often switch to it for small subarrays inside faster sorts like quick sort, because its low overhead wins when n is tiny.

Recap & quick check

Key takeaways

Bubble, selection, and insertion sort are all O(n²) on average.
Bubble sort swaps adjacent out-of-order pairs each pass.
Selection sort makes the fewest swaps; it repeatedly selects the minimum.
Insertion sort is near O(n) on nearly-sorted data and is stable.
In-place = O(1) extra space; stable = equal elements keep their order.

Quick check

1. What does one pass of bubble sort guarantee?

2. Which elementary sort makes the fewest swaps?

3. Insertion sort is especially fast when the data is:

4. A 'stable' sort means:

These are simple but slow. Next we hit the O(n log n) barrier with divide and conquer. Next up: Module 11 — Merge Sort.