Searching and sorting · 25 min

Bubble sort in code: read it, run it, change it

Predict what real code does, run it to check, then change it and write a sort of your own, in Python, JavaScript or TypeScript.

Builds onArrays

01Why it matters

Read code before you write it

Most of programming is reading code: your own from last week, a library's, a colleague's. Yet beginners are usually handed a blank editor first. Classroom studies of an approach called PRIMM found that learners understand more when they first predict what working code does, run it to check, investigate it, modify it, and only then make their own.

That is the plan here, with bubble sort: the simplest sort that actually works. Pick Python, JavaScript or TypeScript; every step works in all three, and your choice is remembered.

02Predict

Predict what one pass does

The outer loop runs passes. In each pass, the inner loop walks along neighbouring pairs and swaps any pair that is out of order. Read the code, then answer before you run anything.

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

03Run it

Run it and check

Now press Run and step through the first pass, five comparisons long. Watch the 9. The narration names the line of code behind every step, and the variables panel shows i and j changing as you go.

04Investigate

Investigate the run

  1. Question 1 of 5

    Why does the inner loop stop at n - 1 - i, not at n - 1?

    Your answer comes back in Review in a few days, so it sticks.

  2. Question 2 of 5

    How many swaps does this code make on an array that is already sorted?

  3. Question 3 of 5

    Which line decides the order the array ends up in?

  4. Question 4 of 5

    What is [2, 3, 4, 1] after the first pass?

  5. Question 5 of 5

    a = [5, 9]. The code runs a[0] = a[1], then a[1] = a[0]. What is a now?

05Modify

Change it: largest first

Make bubble sort put the largest first

This bubble sort works: it sorts arr smallest first. Change it so it sorts **largest first** instead.

Before you edit, predict: how many characters need to change? Then run it and watch the big values sink to the front.

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

06Make

Make your own: selection sort

Selection sort uses the same two moves, compare and swap, in a different plan: find the smallest value that is left, then swap it into the next place. Start by putting its lines in order, then fill the gaps, then write it from scratch.

Write selection sort

Write selection_sort(arr) (Python) or selectionSort(arr) (JavaScript/TypeScript). It sorts arr in place, smallest first.

For each position i, scan the rest of the array for the smallest element, then swap it into position i. That makes exactly one swap per position, however mixed up the array is.

def selection_sort(arr):
    # Sort arr in place, smallest first.
    # Find the smallest remaining element and swap it into place.
    pass

07Explain it back

Say it in your own words

How does bubble sort put an array in order, and why is it finished after n − 1 passes?

08Recap

Recap

  • Read before you write: predict, run, investigate, modify, then make.
  • One pass of bubble sort carries the biggest remaining value to the end, so after i passes the last i values are final.
  • One comparison decides the order, and one swap fixes a pair. Flip the comparison to reverse the order.
  • Next: write insertion sort, or try the bug hunts, where the code is almost right. Then merge sort, which sorts in O(n log n) by merging sorted halves.
Back to path