Insertion sort and selection sort

Code in:JavaC#PythonJavaScript

In short: Insertion sort inserts each element into its place in the sorted part and is fast on nearly sorted input, while selection sort picks the smallest and always makes about n²/2 comparisons.

Problem

The slow products page

The shop sorts the orders of the day by delivery time, and the admin page shows all products by price. Both places use the same old code:

def selection_sort(times):
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
selection_sort(today)
print(" ".join(today))

Output

08:45 09:15 10:30 11:00 14:30 16:45

For six orders it is instant. But there are 50,000 products, and the page takes seconds to open. The code finds the smallest element in the whole rest, puts it in front and repeats. For 50,000 elements that is 49,999 + 49,998 + … + 1 = 1,249,975,000 comparisons. Every time, even when the products are already sorted and only two are swapped.

This lesson has the two basic sorting algorithms: this one, selection sort, and insertion sort. You will count them comparison by comparison and see where each one fits.

The idea

Insertion sort: like cards in your hand

This is how you sort cards in your hand. You take the next card and slide it left, past the bigger ones, until it reaches a smaller one. The cards to its left are always sorted.

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

key is the order being put in place. j starts at the order to its left. While the order at j is later than key, it moves one place right and j goes down. Where the loop stops, there is a gap at j + 1, and key goes there.

In Python times[j] > key compares the strings character by character. The times have a leading zero (09:15), so the order of the text is the order of the time.

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

Output

08:45 09:15 10:30 11:00 14:30 16:45

See it

The cards in place

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

Step by step, in words

1. 6 orders by delivery time. On the left grows the sorted part: at first it is only the first order, 14:30.
2. key = 09:15. 1 later order moves one place right, down to the start, and 09:15 goes to place 0. 1 comparison.
3. key = 11:00. 1 later order moves one place right, up to 09:15, and 11:00 goes to place 1. 2 comparisons.
4. key = 16:45. 14:30 is not later: nothing moves, and 16:45 goes to place 3. 1 comparison.
5. key = 10:30. 3 later orders move one place right, up to 09:15, and 10:30 goes to place 1. 4 comparisons.
6. key = 08:45. 5 later orders move one place right, down to the start, and 08:45 goes to place 0. 5 comparisons.
7. Sorted: 13 comparisons and 10 shifts. The almost sorted list of the day needs only 6 comparisons and 1 shift.

Every card does as much work as there are later cards ahead of it in the sorted part. 16:45 comes after all of them and moves nothing. 08:45 is earlier than all of them and moves all five.

Try it

Count

The same insertion sort, but every comparison and every shift is counted. First on the orders from the scene, then on an almost sorted list: one order arrived a little after the next one.

def insertion_sort(times):
    comparisons = 0
    shifts = 0
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if times[j] <= key:
                break
            times[j + 1] = times[j]
            shifts += 1
            j -= 1
        times[j + 1] = key
    print(f"Comparisons: {comparisons}, shifts: {shifts}")

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"]
insertion_sort(almost)

Output

Comparisons: 13, shifts: 10
08:45 09:15 10:30 11:00 14:30 16:45
Comparisons: 6, shifts: 1

The difference comes from when the inner loop stops. If the order is already after everything on its left, one comparison is enough. So:

• the best case is a sorted list: n - 1 comparisons, zero shifts. O(n);
• the worst case is a reversed list: every order travels to place 0, n(n - 1)/2 comparisons and as many shifts. O(n²);
• on random input every order travels through half of the sorted part on average: about n²/4. Still O(n²).

The almost sorted list is close to the best case: every misplaced order adds a comparison or two.

Try it

Predict the output

The orders are already sorted. What does the counting insertion sort print?

today = ["08:45", "09:15", "10:30", "11:00", "14:30", "16:45"]
insertion_sort(today)

Answer

Comparisons: 15, shifts: 0

Comparisons: 0, shifts: 0

Comparisons: 5, shifts: 0

Check

The idea

Selection sort: pick the earliest

The old code from the start does something else. For place i it looks through the whole rest, finds the earliest order (its index is best: the best so far) and swaps it with the order at i. After that, place i is not touched again.

def selection_sort(times):
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]

Step by step, in words

1. The same 6 orders. Selection sort looks through all that is not sorted yet, finds the earliest order and puts it in front.
2. i = 0: 5 comparisons over the rest. The earliest is 08:45, and it swaps places with 14:30.
3. i = 1: 4 comparisons over the rest. The earliest is 09:15, and it is already in place: no swap.
4. i = 2: 3 comparisons over the rest. The earliest is 10:30, and it swaps places with 11:00.
5. i = 3: 2 comparisons over the rest. The earliest is 11:00, and it swaps places with 16:45.
6. i = 4: 1 comparison over the rest. The earliest is 14:30, and it swaps places with 16:45.
7. 15 comparisons and 4 swaps. The comparisons are always n(n − 1)/2 = 15: the almost sorted list also needs 15, with 1 swap.

def selection_sort(times):
    comparisons = 0
    swaps = 0
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            comparisons += 1
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]
            swaps += 1
    print(f"Comparisons: {comparisons}, swaps: {swaps}")

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
selection_sort(today)
print(" ".join(today))

almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"]
selection_sort(almost)

Output

Comparisons: 15, swaps: 4
08:45 09:15 10:30 11:00 14:30 16:45
Comparisons: 15, swaps: 1

Both lists need 15 comparisons: to be sure it found the earliest one, selection sort looks at the whole rest every time. For n orders that is (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 comparisons on every input. There is no better case.

Its strength is elsewhere: there are at most n - 1 swaps, one per place. Insertion sort shifts up to n²/2 times. When comparing is cheap and moving is expensive (large records that get copied, or writes to flash memory that wears out), the few swaps matter.

See it

Measure

The operation is one comparison of two elements. Insertion sort runs on three inputs: random, almost sorted (sorted, then n/20 neighboring pairs swapped) and reversed. Selection sort runs only on random input, because it does the same on every input.

• Insertion sort, random input O(n²)
• Insertion sort, almost sorted input O(n)
• Insertion sort, reversed input O(n²)
• Selection sort, random input O(n²)

Algorithm	n = 10	n = 100	n = 1,000	n = 10,000	n = 100,000
Insertion sort, random input	37	2,481	254,808	25,057,917	≈ 2,505,791,700
Insertion sort, almost sorted input	9	104	1,049	10,474	104,755
Insertion sort, reversed input	45	4,950	499,500	49,995,000	≈ 4,999,500,000
Selection sort, random input	45	4,950	499,500	49,995,000	≈ 4,999,500,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

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

At 1000 elements: random input 254,808, almost sorted 1,049, reversed 499,500, and selection sort 499,500 on any input. At 100,000 only the almost sorted one runs: the others would make billions of comparisons. The page with 50,000 products is between the two: over a billion comparisons with selection sort.

Try it

Find the bug

This version leaves one order out of place:

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

Output

14:30 08:45 09:15 10:30 11:00 16:45

Pick the line with the bug.

1def insertion_sort(times):2 for i in range(1, len(times)):3 key = times[i]4 j = i - 15 while j > 0 and times[j] > key:6 times[j + 1] = times[j]7 j -= 18 times[j + 1] = key

Check

Try it

Put the lines in order

This is the body of the outer loop of insertion sort. Put it in order.

1. key = times[i]↑↓
2. while j >= 0 and times[j] > key:↑↓
3. times[j + 1] = key↑↓
4. j -= 1↑↓
5. j = i - 1↑↓
6. times[j + 1] = times[j]↑↓

Check

The idea

Where they are used

They are slow for many elements, but they are not only for learning. Insertion sort is the fastest for small arrays and for almost sorted ones: no recursion, no extra memory, and its inner loop is short.

That is why built-in sorts use it inside:

More precisely, if you are curious

• Java. Arrays.sort for objects and Collections.sort are TimSort: it looks for already sorted runs in the data, and extends the short ones with binary insertion sort, up to about 32 elements. Arrays.sort for numbers is dual-pivot quicksort, which sorts the small parts with insertion sort.
• C#. Array.Sort and List<T>.Sort are introsort: a quick sort that switches to insertion sort for parts of up to 16 elements.
• Python. list.sort() and sorted() are TimSort (since 3.11 with the powersort merge rule), and they too extend short runs with binary insertion sort.
• JavaScript. In V8 (Chrome, Node.js) Array.prototype.sort has been TimSort since 2018, with the same binary insertion sort for short runs.

Binary insertion sort finds the place of key with binary search, not one by one. The comparisons become about n log n, but the shifts stay the same.

Large arrays need O(n log n) algorithms. The first one is merge sort.

Exercise

The biggest orders on top

Solve it in your own editor.

By total, largest first. The daily report shows the orders by total, from the largest to the smallest. Write sort_by_total_descending(totals) with insertion sort and sort orders of €46, €13, €89, €23 and €67. The output is:

Output

€89
€67
€46
€23
€13

More tasks

• Selection sort from the back. Write a selection sort that each time finds the latest order and puts it at the end of the unsorted part. Count the comparisons: are they still n(n - 1)/2?
• Shifts against swaps. Run the counting versions on a reversed list of 10 orders. How many shifts does insertion sort make, and how many swaps does selection sort make?
• Binary insertion sort. Find the place of key with binary search in the sorted part, then shift. How many comparisons does it make for 1000 random orders?

Test

Check yourself

1. The order list is already sorted by time, only two neighbors are swapped. Which algorithm finishes faster?

Insertion sort: almost every order is compared once and staysEqually fast: both are O(n²)Selection sort: it makes the fewest swaps

2. How many comparisons does selection sort make for 1000 orders?

499,500, on any inputAbout 10,000About 1000 if they are sorted

3. When is selection sort the better choice?

When there are a million elementsWhen every write to a place is expensive: it makes at most n - 1 swapsWhen the list is almost sorted

4. What does insertion sort do with an order that is earlier than everything in the sorted part?

Shifts all of them one place right and puts it at place 0Leaves it at the endSwaps it with the first one

Check

Start the lesson over

Related lessons

• Builds on: Parameters and return · Time complexity: counting steps · Big-O: how the work grows · Best, average and worst case
• Continues in: Merge sort and "divide and conquer" · Quick sort and the bad pivot · Stable sorting and the built-in sort · Divide and conquer and the recursion tree
• Tasks on this topic: Sorting