10. Sorting: Putting Things in Order

Why order matters

Sorting means rearranging a list so its items follow a rule — usually smallest–to–largest (ascending) or largest–to–smallest (descending). It feels simple, but it is one of the most useful things a computer does, because sorted data unlocks faster algorithms.

Binary search only works on a sorted list. On a sorted list of a million items you can find any value in about 20 comparisons; on an unsorted list you may need a million.
Finding duplicates, the median, or the top 10 all become easy once items sit next to their neighbours.
People read sorted data faster — a phone book, a leaderboard, search results.

Below we learn three classic sorts. To make them easy to compare, every example sorts the same list into ascending order: [5, 2, 4, 1, 3]. Watch how each method reaches the same answer [1, 2, 3, 4, 5] by a different route.

(a) Bubble Sort

Bubble sort repeatedly walks through the list, comparing each pair of neighbours and swapping them if they are in the wrong order. After each full pass the largest remaining value "bubbles" to the end.

Problem

Sort the list [5, 2, 4, 1, 3] into ascending order using bubble sort.

Pseudocode

BUBBLE_SORT(a):
    swapped = True
    WHILE swapped:
        swapped = False
        FOR i FROM 0 TO length(a) - 2:
            IF a[i] > a[i+1]:
                swap a[i] and a[i+1]
                swapped = True
    RETURN a

Trace table

The array state after each complete pass over [5, 2, 4, 1, 3]:

Pass	Swaps made this pass	Array after the pass
start	—	[5, 2, 4, 1, 3]
1	(5,2)(5,4)(5,1)(5,3)	[2, 4, 1, 3, 5]
2	(4,1)(4,3)	[2, 1, 3, 4, 5]
3	(2,1)	[1, 2, 3, 4, 5]
4	none → stop	[1, 2, 3, 4, 5]

In Python

def bubble_sort(a):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(a) - 1):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
    return a

print(bubble_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

(b) Selection Sort

Selection sort builds the sorted list one slot at a time. On each pass it scans the unsorted part, finds the smallest remaining value, and swaps it into the next position from the front.

Problem

Sort [5, 2, 4, 1, 3] into ascending order using selection sort.

Pseudocode

SELECTION_SORT(a):
    FOR i FROM 0 TO length(a) - 2:
        min = i
        FOR j FROM i+1 TO length(a) - 1:
            IF a[j] < a[min]:
                min = j
        swap a[i] and a[min]
    RETURN a

Trace table

The array state after each pass places one more value in its final position (shown in bold conceptually at the front):

Pass (i)	Smallest found in unsorted part	Array after swap into slot i
start	—	[5, 2, 4, 1, 3]
0	1 (at index 3)	[1, 2, 4, 5, 3]
1	2 (already at index 1)	[1, 2, 4, 5, 3]
2	3 (at index 4)	[1, 2, 3, 5, 4]
3	4 (at index 4)	[1, 2, 3, 4, 5]

In Python

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

print(selection_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

(c) Insertion Sort

Insertion sort grows a sorted region on the left. It takes the next item and slides it leftward past any larger items until it drops into the right place — exactly how many people sort a hand of playing cards.

Problem

Sort [5, 2, 4, 1, 3] into ascending order using insertion sort.

Pseudocode

INSERTION_SORT(a):
    FOR i FROM 1 TO length(a) - 1:
        key = a[i]
        j = i - 1
        WHILE j >= 0 AND a[j] > key:
            a[j+1] = a[j]
            j = j - 1
        a[j+1] = key
    RETURN a

Trace table

After inserting each new key into the sorted left region of [5, 2, 4, 1, 3]:

i	key being inserted	Array after insertion
start	—	[5, 2, 4, 1, 3]
1	2	[2, 5, 4, 1, 3]
2	4	[2, 4, 5, 1, 3]
3	1	[1, 2, 4, 5, 3]
4	3	[1, 2, 3, 4, 5]

In Python

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

print(insertion_sort([5, 2, 4, 1, 3]))

Output:

[1, 2, 3, 4, 5]

Compare the three: all three turn [5, 2, 4, 1, 3] into [1, 2, 3, 4, 5]. Bubble sort swaps neighbours many times, selection sort makes few swaps but always scans the rest, and insertion sort does little work when the data is already nearly sorted.