Bubble, selection and insertion sort in Python

Why this lesson comes first

Sorting means putting items in order: numbers from smallest to largest, names from A to Z, students from the highest mark to the lowest. Almost every program that shows a list to a person sorts something somewhere. In Python you will usually call the built-in sorted() function, which does the work for you. You still need to understand sorting, for three reasons.

The first reason is that the simple sorts teach the habits that every later algorithm uses: a loop that moves through a list, a swap of two values, and a fact that stays true while the loop runs. That fact has a name, an invariant. Once you can spot the invariant in a simple sort, you can spot it in merge sort, quick sort, heaps and dynamic programming.

The second reason is that interviewers ask about these sorts directly. "Which sort is best for an almost sorted list?" and "Why does insertion sort need to shift values?" are common opening questions. You should be able to answer both from a trace, not from memory.

The third reason is that these sorts are the right tool in a few real places. Insertion sort is used inside the standard library for small pieces of a bigger sort, because it is fast on tiny inputs. Knowing when the simple sort wins is part of knowing when the fancy sort is worth its extra code.

This lesson covers three sorts: bubble sort, selection sort and insertion sort. All three run in O(n squared) time in the worst case. The notation O(n squared) is a way of saying "the work grows with the square of the list length." If the list doubles in size, the work becomes about four times bigger. You will meet the full notation in the complexity module. For now, read O(n squared) as "about n times n steps."

What the computer does when it sorts

Before any code, picture the data. A Python list of five numbers is five boxes in a row. Each box has a number called an index, starting from 0. The first box is index 0, the last box is index 4. You read a box with a[2] and you write it with a[2] = 7.

A sort needs only two actions on those boxes.

1. A comparison asks a question about two boxes, such as "is the value at index 1 bigger than the value at index 2?"
2. A swap exchanges the values of two boxes.

Every simple sort is a plan for when to compare and when to swap. The cost of a sort is mostly the number of comparisons plus the number of swaps. When you count the cost, count those two things.

In many languages a swap needs a third variable, because if you copy one value over the other you lose it. Python lets you write the swap in one line, using a tuple (a fixed group of values, such as a, b) on each side of the assignment.

a[i], a[j] = a[j], a[i]

Python builds the pair (a[j], a[i]) on the right side first, with both old values. Then it stores the first value into a[i] and the second into a[j]. No value is lost, so no temporary variable is needed. You will see this line in all three sorts.

A plain function is enough for these sorts. Python has no static keyword, so a function defined at the top level of a file simply belongs to the file. You call it with its name and the list.

Bubble sort

Analogy. Picture a row of people of different heights, and you want them ordered from shortest to tallest. Walk down the row. Each time two neighbours are in the wrong order, swap them. After one walk, the tallest person is at the far end, because every time they met a neighbour they swapped past them. That is why the method is called bubble sort: the largest value rises to the end like a bubble rising in water.

The idea. One pass means one walk from the left end to the right end. A pass compares each pair of neighbours and swaps when the left one is bigger. After pass 1, the largest value is in its final place at the end. After pass 2, the second largest is in its place just before it. Each pass fixes one more value at the right end, so the next pass can stop one box earlier.

The code has two loops. The outer loop counts passes. The inner loop walks the pairs.

def bubble_sort(a):
    for pass_number in range(len(a) - 1):
        swapped = False
        for i in range(len(a) - 1 - pass_number):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break    # a pass with no swaps means the list is sorted

Two things differ from a Java version of this code. The loop variable cannot be called pass, because pass is a keyword in Python, a word with a fixed meaning to the language. This code uses pass_number. Also, range(len(a) - 1) produces the numbers 0, 1, ..., len(a) - 2. The end value of range is never included, so the loop runs len(a) - 1 times, which is the number of passes we need.

Look at the inner loop limit: len(a) - 1 - pass_number. After pass_number passes, the last pass_number boxes already hold the largest values, so there is no need to compare them again. That limit is one of the places where beginners make mistakes, and we come back to it in the common mistakes section.

The swapped flag is an optimisation. If a whole pass makes no swap, every neighbour pair is already in order, so the list is sorted and the outer loop can stop. You will see the effect in the examples below.

Step through the sort below. Watch the big values move to the right end one pass at a time.

Now trace the code by hand on [5, 2, 4, 1]. Write down the list after every swap.

• Pass 1, i = 0: compare 5 and 2. 5 is bigger, swap. The list is [2, 5, 4, 1].
• Pass 1, i = 1: compare 5 and 4. Swap. The list is [2, 4, 5, 1].
• Pass 1, i = 2: compare 5 and 1. Swap. The list is [2, 4, 1, 5]. The inner loop uses range(3), so i = 2 is its last comparison in pass 1.
• Pass 2, i = 0: compare 2 and 4. No swap.
• Pass 2, i = 1: compare 4 and 1. Swap. The list is [2, 1, 4, 5].
• Pass 2: the inner loop uses range(len(a) - 1 - 1), which is range(2), so it stops after i = 1.
• Pass 3, i = 0: compare 2 and 1. Swap. The list is [1, 2, 4, 5].
• The outer loop uses range(3), so after pass 3 it has no more passes, and the sort ends.

The result is [1, 2, 4, 5]. Notice that after pass 1 the value 5 is in its final place. After pass 2 the value 4 is in its final place. The sort never has to look at the last box again.

The complexity is easy to read from the code. In the worst case, the list is in reverse order, every pass swaps every pair, and the loops do about n times n divided by 2 comparisons. That is O(n squared). In the best case, the list is already sorted, the first pass makes no swaps, the flag stops the sort, and the work is only n minus 1 comparisons. That is O(n). Bubble sort uses O(1) extra space, which means a fixed number of extra variables, no matter how long the list is.

Selection sort

Analogy. Imagine a line of students waiting to be sorted by height. You walk along the unsorted part, find the shortest person, and move that person to the front of the unsorted part. Then you do the same for the rest of the line. Each time you choose the next smallest value, which is where the name selection comes from.

The idea. Selection sort keeps a boundary. Everything to the left of the boundary is sorted and holds the smallest values, in order. Everything to the right is not sorted yet. Each round finds the smallest value on the right side and swaps it onto the boundary, then moves the boundary one step right.

def selection_sort(a):
    for i in range(len(a) - 1):
        smallest = i                         # index of the smallest value found so far
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j                 # remember the index, not the value
        a[i], a[smallest] = a[smallest], a[i]   # one swap per round, at most

Two details matter here. First, the variable smallest stores an index, not a value. The comparison a[j] < a[smallest] reads the value at smallest, so the stored index always points at the current smallest value. Second, the swap happens after the inner loop, not inside it. Swapping inside the inner loop would change the list while you are still searching, and you would get a different and slower algorithm.

Step through it below. Notice that the search runs every time, even when the next value is already in place.

Trace the code on [64, 25, 12, 22, 11].

• Round 1, i = 0: the search finds 11 at index 4. Swap index 0 and index 4. The list is [11, 25, 12, 22, 64].
• Round 2, i = 1: the search over indexes 1 to 4 finds 12 at index 2. Swap index 1 and index 2. The list is [11, 12, 25, 22, 64].
• Round 3, i = 2: the search over indexes 2 to 4 finds 22 at index 3. Swap index 2 and index 3. The list is [11, 12, 22, 25, 64].
• Round 4, i = 3: the search over indexes 3 to 4 finds 25 at index 3, which is already the smallest. The swap puts index 3 onto itself, so nothing changes.

Count the work. The first round compares four pairs, the second round three, the third round two and the fourth round one. That is 4 + 3 + 2 + 1 = 10 comparisons for five values. For n values, the count is always (n - 1) + (n - 2) + ... + 1, which equals n times (n - 1) divided by 2. Selection sort does this many comparisons even when the input is already sorted. The number of swaps is at most n minus 1. That is why selection sort is sometimes chosen when a swap is expensive. For example, when each value is a large object that takes a long time to move, you want as few moves as possible.

Insertion sort

Analogy. Think about sorting playing cards in your hand. You pick up one new card at a time. You slide it left past every card that is bigger, and you stop when the card to the left is smaller or equal. The cards you already hold are always in order. Insertion sort does exactly this with the values in a list.

The idea. The left part of the list is always sorted. At the start, the sorted part is just index 0, which is one value and therefore already sorted. For each new position i, take the value there, call it the key, and shift every bigger value in the sorted part one box to the right. Then drop the key into the gap.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]                        # the card we are placing
        j = i - 1                         # start at the right end of the sorted part
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]               # shift the bigger value one box right
            j -= 1
        a[j + 1] = key                    # drop the key into the gap

The order of the two tests in the while line matters. Python checks j >= 0 first, because and stops at the first false test. When j becomes -1, the loop stops before it reads a[-1]. Python does not crash on a negative index. It reads from the end of the list instead, which is a silent error. The common mistakes section shows what that looks like.

Step through it below. The shaded box is the key, and the sorted part grows from the left.

Trace the code on [5, 2, 4, 1].

• i = 1, key 2. The value 5 is bigger than 2, so shift 5 right. The gap is at index 0. Drop 2 in. The list is [2, 5, 4, 1].
• i = 2, key 4. The value 5 is bigger than 4, so shift it right. The value 2 is smaller than 4, so stop. Drop 4 into the gap. The list is [2, 4, 5, 1].
• i = 3, key 1. Shift 5, then 4, then 2, because each one is bigger than 1. The index j reaches -1 and the loop stops. Drop 1 at index 0. The list is [1, 2, 4, 5].

Notice the difference from selection sort. Insertion sort does a lot of work when the input is in reverse order, because every new key must travel all the way to the left. It does almost no work when the input is nearly sorted, because each key is already close to its place and the while loop stops at once. For a list that is already sorted, the loop makes one comparison per position and no shifts, so the total is n minus 1 comparisons. That is O(n) best case.

Bubble, selection and insertion compared

Now compare the three sorts on the same six properties that interviewers ask about.

Stable means that when two values are equal, the one that came first in the input still comes first in the output. Students with the same grade stay in the order they were listed. This matters when a list is sorted in several steps, such as first by name and then by grade. The fourth lesson in this module explains stability in full. For now, notice that bubble and insertion keep equal values in their original order because they only move a value past a bigger value, never past an equal one. Selection sort can break that order, as the next example shows.

Worked example 1: selection sort breaks stability. Give the list ("2a", 2), ("2b", 2), ("1", 1). Each item is a pair, the label and the number, and the sort compares only the number. In round 1, the search finds 1 at index 2 and swaps it with index 0. The list becomes ("1", 1), ("2b", 2), ("2a", 2). Now 2b comes before 2a, although 2a was first in the input. The sort is correct, because the numbers are in order, but the tied items changed places.

Running the sorts in Python

You now have three functions. To see them work, call each one on a list and print the result. The programs below have their data built in, so you can run them without typing input.

The first program is bubble sort with a print after every pass.

The output is:

after pass 1: [2, 4, 1, 3, 5]
after pass 2: [2, 1, 3, 4, 5]
after pass 3: [1, 2, 3, 4, 5]
after pass 4: [1, 2, 3, 4, 5]
sorted: [1, 2, 3, 4, 5]

Check pass 1 with the trace method. The big value 5 moves to the end, and the other values shift just enough. Pass 4 prints the same list as pass 3, and that is correct: pass 3 made a swap, so the flag did not stop the loop. Pass 4 made no swap, so swapped is False, the line if not swapped: runs, and the sort ends.

Python needs no import line for this program, because print, range and len are built into the language. Other tools, such as heapq or bisect, live in modules that must be imported first. Common mistakes below shows the error you get when a name is missing.

The second program is selection sort. It counts the comparisons and swaps, and it prints after each round. The function returns the two counts, so the caller can print them.

The output is:

step 1: [11, 25, 12, 22, 64]
step 2: [11, 12, 25, 22, 64]
step 3: [11, 12, 22, 25, 64]
step 4: [11, 12, 22, 25, 64]
comparisons: 10
swaps: 3

The four steps match the trace above. The comparison count is 10, which is 4 + 3 + 2 + 1. The swap count is 3, not 4, because step 4 found the smallest value already in place and skipped the swap. The if smallest != i: check is a small improvement on the plain version. It does not change the number of comparisons.

The third program is insertion sort with a print after every insert.

The output is:

insert 2 -> [1, 2, 4, 3, 5, 6]
insert 4 -> [1, 2, 4, 3, 5, 6]
insert 3 -> [1, 2, 3, 4, 5, 6]
insert 5 -> [1, 2, 3, 4, 5, 6]
insert 6 -> [1, 2, 3, 4, 5, 6]
shifts: 1

Look at the first two lines. The key 2 has nothing bigger in front of it, so the loop makes no shift and the list does not change. The key 4 also stays where it is. Only the key 3 moves, and it moves one place, past the 4. The input was nearly sorted, so insertion sort did almost no work: one shift for six numbers.

Worked examples with the counting

Counting the steps is the skill interviewers look for. The next examples show the count for each sort on specific inputs. Trace them on paper before you read the answer.

Worked example 2: bubble sort on a sorted list. Input [1, 2, 3, 4, 5, 6, 7, 8]. Pass 1 compares 7 neighbour pairs and makes no swap. The flag stays False, so the loop breaks after pass 1. Total comparisons: 7. The swapped flag is the reason the work is only n minus 1.

Worked example 3: bubble sort on a reversed list. Input [4, 3, 2, 1]. Pass 1 makes three swaps and moves 4 to the end. Pass 2 makes two swaps and moves 3 into place. Pass 3 makes one swap. Total comparisons: 3 + 2 + 1 = 6, which is n times (n - 1) divided by 2. The flag never stops the loop early, because every pass makes a swap.

Worked example 4: insertion sort on a reversed list. Input [4, 3, 2, 1]. The key 3 shifts past 4 (one shift). The key 2 shifts past 4 and 3 (two shifts). The key 1 shifts past 4, 3 and 2 (three shifts). Total shifts: 1 + 2 + 3 = 6. That is the worst case for insertion sort, and it equals the number of comparisons in bubble sort on the same input.

Worked example 5: selection sort on a sorted list. Input [1, 2, 3, 4]. Round 1 compares 3 pairs, round 2 compares 2, round 3 compares 1. Total comparisons: 6. No value moves, because each round finds its own index as the minimum. Selection sort does the same work on sorted input as on random input, which is the reason it is never the best choice when the input is nearly sorted.

Worked example 6: count the work on the same input. Use [3, 1, 2]. Bubble sort: pass 1 compares 3 with 1 (swap), then 3 with 2 (swap), giving [1, 2, 3]. Pass 2 compares 1 with 2, no swap, and the flag stops the sort. Work: 2 + 1 = 3 comparisons and 2 swaps. Selection sort: round 1 finds 1 at index 1 and swaps it with index 0, giving [1, 3, 2]. Round 2 finds 2 at index 2 and swaps it with index 1. Work: 2 + 1 = 3 comparisons and 2 swaps. Insertion sort: key 1 is compared with 3 and shifts it (1 comparison, 1 shift), then the loop stops because the index is -1. Key 2 is compared with 3 and shifts it (1 comparison, 1 shift), then compared with 1 and stops (1 comparison). Work: 3 comparisons and 2 shifts. The counts are close because the input is tiny. For large inputs the gap becomes large.

The next program prints the comparison counts of the three sorts side by side, so you can see the gap for yourself. It copies each list before sorting it, so each sort starts from the same data. The function list(a) makes the copy.

The output has two blocks, one for the sorted input and one for the reversed input:

bubble comparisons: 7
selection comparisons: 28
insertion comparisons: 7
all three agree: True
sorted: [1, 2, 3, 4, 5, 6, 7, 8]
bubble comparisons: 28
selection comparisons: 28
insertion comparisons: 28
all three agree: True
sorted: [1, 2, 3, 4, 5, 6, 7, 8]

The sorted input shows the strengths: bubble and insertion do 7 comparisons, while selection still does 28. The reversed input shows the worst case: all three do 28 comparisons, which is n times (n - 1) divided by 2. Eight numbers already show the difference. For a list of one million numbers, the same pattern means about half a trillion steps, which is why none of these three sorts is used on large data.

The program also prints all three agree. It is a habit worth copying. When you rewrite a sort, run the old and new versions on the same input and check that the outputs match. A changed comparison can break the order silently, and a check like this catches it at once.

Python also has a built-in way to check the result of your own sort. The sorted() function returns a new sorted list and leaves the input unchanged. Comparing your result with sorted(data) is a quick test of correctness.

What happens inside the machine

When Python runs bubble_sort(numbers), it creates a new frame on the call stack. A frame is a small block of memory that holds the function's parameters and local variables, such as pass_number and swapped. The list itself is not copied. The parameter a refers to the one list object in memory. Inside the function, a[i], a[i + 1] = ... changes that single list, so the caller sees the change as soon as the function returns.

Inside a loop, the machine does the same few steps again and again: read two values, compare them, maybe write two values. The cost of a single comparison is tiny, a few nanoseconds on a modern computer. The cost of a sort comes from how many times that tiny step runs. This is why counting steps is more useful than timing a program. The count tells you how the cost grows, and that does not depend on the speed of one computer.

Python adds a cost that C or Java code does not pay. Each a[i] is a lookup through the list object, and each integer is an object too. Python integers have no fixed size, so the number 5 and the number 5000000000 are both valid. That flexibility costs memory and time. For that reason a Python loop that does a million comparisons is much slower than the same loop written in C. The count of steps still tells you how the cost grows.

Common mistakes and their messages

Each mistake below comes with the message you will see. Reading the message is a skill, so the first time you see a message, read it from the bottom up. The last line names the error type and the reason.

Mistake 1: the inner loop reads past the end. Suppose you write the bubble loop with for i in range(len(a)): and compare a[i] with a[i + 1]. At the last index, a[i + 1] is one box past the end of the list. Python stops the program and prints a traceback, the list of lines that shows where the error happened. This version of the bubble loop, run on [5, 2, 4, 1], produces the output after the code:

def bubble_sort(a):
    for i in range(len(a)):
        if a[i] > a[i + 1]:
            a[i], a[i + 1] = a[i + 1], a[i]
 
bubble_sort([5, 2, 4, 1])

The output is:

Traceback (most recent call last):
  File "bubble.py", line 6, in <module>
    bubble_sort([5, 2, 4, 1])
    ~~~~~~~~~~~^^^^^^^^^^^^^^
  File "bubble.py", line 3, in bubble_sort
    if a[i] > a[i + 1]:
              ~^^^^^^^
IndexError: list index out of range

The first path depends on where you saved the file, so it will differ on your machine. Read it from the bottom. The last line names the exception type, IndexError, and the reason, list index out of range. The line above it shows the code that failed, with a ~ and ^ under the part that broke. The fix is range(len(a) - 1 - pass_number) in the inner loop, which stops one box before the end.

Mistake 2: testing a negative index. In insertion sort, a beginner may write the while line as while a[j] > key and j >= 0:. When j reaches -1, Python does not stop. It reads a[-1], which is the last value of the list, and it does not raise an error. Python counts negative indexes from the end: -1 means the last box, -2 the one before it. In this sort the final list still comes out right, because the loop stops at -1 either way. In other code, a silent read like this can give a wrong answer. The fix is to put j >= 0 first, so the program never reads a negative index. Python's and checks its left side first and stops when that side is false, so the order decides what gets read.

The following program shows the silent read:

The output is:

1
Traceback (most recent call last):
  File "index.py", line 3, in <module>
    print(a[len(a)])
          ~^^^^^^^^
IndexError: list index out of range

The first line prints 1, which is the last value, and no error was raised. The second line asks for index 4 on a list of length 4, and that does raise IndexError. The traceback lines are shown the same way as in Mistake 1, and the file name depends on where you saved the file. Negative indexes are a Python feature that is useful, for example a[-1] to read the last item, and it is also a trap in loop code.

Mistake 3: comparing values of different types. Python compares numbers with numbers and text with text. If a list holds both, the comparison fails. In Java, the matching mistake is an array of the wrong type, and the compiler stops it before the program runs. In Python, the error appears only when the comparison runs:

The output is:

Traceback (most recent call last):
  File "mixed.py", line 1, in <module>
    print(sorted([3, "a", 1]))
          ~~~~~~^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'str' and 'int'

The last line says the < comparison has no meaning for a string and an integer. The fix is to make the list hold one type, for example by converting every item with int() or str() before the sort. The type of the error is TypeError, which means the operation does not fit the types of its values.

Mistake 4: forgetting that the list is changed in place. Calling bubble_sort(numbers) changes numbers. It returns None. If you write result = bubble_sort(numbers) and then print result, you get None. This is not an error in the sort. It is a rule about Python lists. Functions that change a list in place return None by convention. The built-in sorted() is different: it returns a new list and leaves the original alone. Use the form that matches your intent.

Mistake 5: using >= in insertion sort. Changing a[j] > key to a[j] >= key does not crash. The program still sorts, but it moves equal values past each other, so stability is lost. Test it with two equal values with different labels to see the change. The next program does that with pairs. It uses >= in the insertion sort, and the output shows the label order changed.

The output is:

[('1', 1), ('2b', 2), ('2a', 2)]
[('1', 1), ('2a', 2), ('2b', 2)]

The first line is the broken version. The label 2b came before 2a, which is the wrong order for a stable sort. The second line is the built-in sorted() with a key function. It keeps 2a before 2b, because Python's built-in sort is stable. This is the kind of bug that passes a quick test and fails in a real system, so the habit is to test equal values on purpose.

Mistake 6: swapping inside the selection search. Writing the swap inside the inner loop, rather than after it, makes a different algorithm. The list changes while you are still looking for the minimum, so later comparisons use new values. The result may still be sorted, but the count of comparisons and swaps no longer matches the analysis, and interviewers will notice.

Mistake 7: starting the outer loop at the wrong index. Insertion sort starts at index 1 because index 0 alone is already a sorted group of one. Starting at index 0 is harmless for this code, since the inner loop does nothing. The mistake that hurts is range(1, len(a) + 1). That makes a[i] read one box past the end on the last pass, and Python raises the same IndexError: list index out of range as in Mistake 1.

Debugging walkthrough

Here is a broken bubble sort. It is meant to sort [3, 1, 2] into ascending order, but the result is wrong. Before you read further, try to find the bug yourself using the trace method.

def bubble_sort(a):
    for i in range(len(a)):
        for j in range(len(a) - 1):
            if a[j] < a[j + 1]:          # bug is on this line
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

Trace it. Pass 1 compares 3 and 1. Since 3 < 1 is false, nothing happens. Compare 1 and 2: 1 < 2 is true, so the code swaps them. The list becomes [3, 2, 1]. The loop keeps going with the same rule, and the result is descending order, not ascending. The bug is the comparison operator, which should be >, not <. Swap the sign and the sort works. Notice that the outer loop also runs len(a) passes, which is correct but wasteful. The extra passes waste some work, but the wrong order comes from the comparison alone.

Run the broken version to see the result:

The output is [3, 2, 1], which is descending order.

The method used in this walkthrough is the one a professional uses when a sort is wrong:

1. Write down a tiny input, with three or four values.
2. Predict the list after the first comparison and the first swap.
3. Print the list after each pass, as the first runnable program did.
4. Find the first step where the real output differs from your prediction.
5. Look at the line that made that step. The bug is almost always there.

Do not guess. A print statement takes seconds to add and removes the guessing.

Variations and edge cases

Every sort should be tested on a few inputs that break naive code. Check these cases before you trust a sort.

• Empty list. The range(len(a) - 1) on an empty list is range(-1), which produces no numbers, so the loop does not start. The code is safe, but only if you check.
• One value. Every sort should leave a single value unchanged. Insertion sort starts at index 1, so it never runs.
• All values equal. Bubble sort with the flag stops after one pass. Selection sort still does all its comparisons.
• Negative numbers. Comparisons work the same for negative values, so the sort needs no special case.
• Descending sort. Flip the comparison. In bubble sort, change a[i] > a[i + 1] to a[i] < a[i + 1]. Now the smallest value sinks to the end on each pass, so the end fills with the smallest values in order and the same loop limits still work. The practice exercises ask you to do this.

A short test list like this one is the start of professional testing. You will use it in every module.

Interview questions

Question: Which of the three sorts is best for a list that is almost sorted? Answer: insertion sort. Each new key moves only a short distance, so the total work is close to n. Bubble sort with the flag is also good. Selection sort is the worst choice, because it does n squared comparisons even on sorted input. A strong answer also mentions stability: insertion sort keeps equal values in order.

Question: Why does selection sort make at most n minus 1 swaps? Answer: it makes at most one swap per round, and there are n minus 1 rounds. Each round puts one value in its final place. Bubble and insertion sort can make many more swaps or shifts, because a value may move past many neighbours.

Question: Why is bubble sort rarely used? Answer: its many swaps are slow on real hardware, it has no advantage over insertion sort, and it does more comparisons on average. A good answer shows that you know it is a teaching sort, not a production sort.

Question: What is an invariant in insertion sort? Answer: at the start of each round, the values from index 0 to i - 1 are in sorted order. A good answer points to the line of code that keeps the fact true after each round.

Real-world uses

Insertion sort is used inside production sorting code for small pieces of data. Python's built-in sort, called Timsort, uses insertion sort on short runs of values before it merges the runs together. Many other library sorts switch to insertion sort when the piece is a few dozen values or fewer, because the overhead of the fancy method is larger than the saving. The same idea appears in databases, where a small set of rows is sorted in memory before it goes to disk.

Selection sort is useful when writes are expensive, such as writing to flash memory with a limited number of erase cycles. Its at most n minus 1 swaps keep the number of writes low, even though it does more reads.

Bubble sort is mainly a teaching tool. You will still see it in exercises, in early programming courses and in quick scripts that sort a dozen values once.

Practice

Try each exercise on paper first. Check your answer after you have made an attempt.

1. Trace bubble sort on [3, 2, 1]. Write the list after each swap and count the swaps.

Show the answer

Pass 1: [3, 2, 1] becomes [2, 3, 1] after the first swap and [2, 1, 3] after the second. Pass 2: [2, 1, 3] becomes [1, 2, 3]. The outer loop uses range(2), so there are only two passes, and the sort ends after pass 2. Total swaps: 3.

2. Change bubble_sort so it sorts in descending order, with the biggest value first. Hint: flip one comparison.

Show the answer

Change if a[i] > a[i + 1]: to if a[i] < a[i + 1]:. Each pass now carries the smallest value of the unsorted part to the end. The boxes at the end fill with the smallest values first, in order, so the list ends in descending order. The same loop limits work, and the code needs no other change.

3. Which of the three sorts finishes first on [1, 2, 3, 4, 5]? Count the comparisons for each.

Show the answer

Bubble sort with the flag: pass 1 makes 4 comparisons with no swaps, then stops. Insertion sort: 4 comparisons, one per new key, with no shifts. Selection sort: 4 + 3 + 2 + 1 = 10 comparisons. Bubble and insertion tie at 4 comparisons. Selection is the slowest.

4. Count the comparisons selection sort makes on six values, without running the code. Then check your answer with the formula.

Show the answer

5 + 4 + 3 + 2 + 1 = 15. The formula n times (n - 1) divided by 2 gives 6 times 5 divided by 2, which is 15.

5. A student writes the insertion sort outer loop as for i in range(1, len(a) + 1): and runs it on a list of length 6. Explain what happens and give the message.

Show the answer

When i is 6, the statement key = a[i] reads index 6 of a list whose valid indexes are 0 to 5. Python raises IndexError: list index out of range. The fix is range(1, len(a)).

6. Write insertion_sort so it sorts in descending order, biggest first.

Show the answer

Change the while condition to while j >= 0 and a[j] < key:. Keys now move left past smaller values, so the largest values gather at the front.

7. Add a comparisons counter to bubble sort. Predict the count for [8, 7, 6, 5, 4, 3, 2, 1] before you run it, then run it to check.

Show the answer

The reversed list of 8 values needs 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons, and the flag never stops the loop early. Add comparisons += 1 at the start of the inner loop body, before the if, to get 28.

8. Write a function is_sorted(a) that returns True when every value is less than or equal to the next one. It should take one pass and no sorting.

Show the answer

def is_sorted(a):
    for i in range(len(a) - 1):
        if a[i] > a[i + 1]:
            return False
    return True

The loop runs n minus 1 times, so the check is O(n). The built-in version of this check is a == sorted(a), which also works, but it sorts the list first, so it does more work than the loop above.

9. Make selection sort work on a list of strings. Explain why the comparison in the code works without changes.

Show the answer

The < operator works on strings in Python. It compares them in alphabetical order, using the character codes of each letter. So "apple" < "banana" is True, and the selection sort code needs no change. The same is true for any values with a defined <, such as numbers or tuples. Only a list that mixes types, as in Mistake 3, breaks the comparison.

10. Explain why insertion sort is stable when the test is a[j] > key, but not when it is a[j] >= key. Use the pairs ("2a", 2) and ("2b", 2) as an example.

Show the answer

With >, the loop stops at an equal value, so ("2b", 2) never moves past ("2a", 2). The original order is kept. With >=, the loop moves past the equal value, so ("2b", 2) slides in front of ("2a", 2), and the order changes. Stability depends on the strict comparison.

What you now know

• Sorting uses comparisons to decide order and swaps or shifts to move values.
• Python swaps two items in one line, a[i], a[j] = a[j], a[i], with no temporary variable.
• Bubble sort moves the largest value to the end on each pass, and its flag makes sorted input O(n).
• Selection sort finds the smallest value on each round and does at most n minus 1 swaps, but always does about n squared comparisons.
• Insertion sort grows a sorted left part and shifts each new key into place. It is O(n) on nearly sorted input and is the right choice for small or nearly sorted data.
• All three sorts are O(n squared) in the worst case. Bubble and insertion are stable. Selection is not, in general.
• Python raises IndexError for a too-large index, but it silently reads from the end for a negative one. Test the index bounds first.
• Test a sort with an empty list, one value, equal values and reversed values. Read the traceback from the bottom line up.