Bubble sort and its improvements

Worst-case version (spec 10.3.3)

Make n - 1 passes. In each pass compare every adjacent pair and swap if the left one is bigger. After each pass the largest remaining item has 'bubbled' to its final place.

def bubble_sort_basic(items):
    n = len(items)
    for p in range(n - 1):
        for i in range(n - 1):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
        print("after pass", p + 1, items)

bubble_sort_basic([5, 1, 4, 2, 8])

Output:

after pass 1 [1, 4, 2, 5, 8]
after pass 2 [1, 2, 4, 5, 8]
after pass 3 [1, 2, 4, 5, 8]
after pass 4 [1, 2, 4, 5, 8]

Improvement 1: reduce the upper bound

After pass k, the last k items are in place, so each pass can stop one place earlier. This saves comparisons: n - 1, then n - 2, and so on.

Improvement 2: exit when no swaps

If a whole pass makes no swaps, the list is sorted and the algorithm can stop. Use a swapped flag and a while loop.

def bubble_sort(items):
    upper = len(items) - 1
    swapped = True
    passes = 0
    while swapped and upper > 0:
        swapped = False
        for i in range(upper):
            if items[i] > items[i + 1]:
                temp = items[i]
                items[i] = items[i + 1]
                items[i + 1] = temp
                swapped = True
        upper = upper - 1
        passes = passes + 1
    return passes

data = [5, 1, 4, 2, 8]
print(bubble_sort(data), data)

Output:

3 [1, 2, 4, 5, 8]

The sort is in place: it changes the list it is given. Swapping needs a temporary variable, or Python's a, b = b, a.

Worked example

Show the first pass of bubble sort on [6, 3, 8, 2].

1. Compare 6, 3: swap gives [3, 6, 8, 2]
2. Compare 6, 8: no swap
3. Compare 8, 2: swap gives [3, 6, 2, 8]

Answer: [3, 6, 2, 8] (8 is now in its final place)

Check yourself

1. What is displayed when this code runs? ```python data = [7, 2, 9, 4, 1] for i in range(len(data) - 1): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] print(data) ```
   Show answer

   [2, 7, 4, 1, 9]. One pass moves the largest value, 9, to the end: [2, 7, 4, 1, 9].

2. How many swaps does the first pass of bubble sort make on [7, 2, 9, 4, 1]?
   Show answer

   3. 7 and 2 swap, 7 and 9 do not, 9 and 4 swap, 9 and 1 swap: 3 swaps.

3. With the reduced upper bound, how many comparisons does bubble sort make in total on a list of 6 items if it needs all 5 passes?
   Show answer

   15. 5 + 4 + 3 + 2 + 1 = 15 comparisons.

4. The basic worst-case bubble sort makes n - 1 passes of n - 1 comparisons. How many comparisons is that for 6 items?
   Show answer

   25. 5 passes of 5 comparisons = 25.

5. What is displayed when this code runs? ```python def bubble_sort(items): upper = len(items) - 1 swapped = True passes = 0 while swapped and upper > 0: swapped = False for i in range(upper): if items[i] > items[i + 1]: items[i], items[i + 1] = items[i + 1], items[i] swapped = True upper = upper - 1 passes = passes + 1 return passes print(bubble_sort([1, 2, 3, 5, 4])) ```
   Show answer

   2. Pass 1 swaps 5 and 4; pass 2 makes no swaps, so the sort stops after 2 passes.

6. This bubble sort is missing a line in the swap. Which line completes it? ```python items = [4, 3, 1, 2] for p in range(len(items) - 1): for i in range(len(items) - 1 - p): if items[i] > items[i + 1]: temp = items[i] items[i] = items[i + 1] __________ print(items) ```
   • `items[i + 1] = temp`
   • `items[i + 1] = items[i]`
   • `temp = items[i + 1]`
   • `items[i] = temp`
   Show answer

   `items[i + 1] = temp`. The value saved in temp must go into the right-hand position to finish the swap.

7. What does it mean that bubble sort is an in-place sort?
   • It only works on lists already in place
   • It leaves the original list unchanged
   • It rearranges the items within the original list without needing a second list
   • It returns a new sorted copy
   Show answer

   It rearranges the items within the original list without needing a second list. In-place sorts change the list they are given and need only a temporary variable for swaps.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (XCP01/YCP01), first teaching 2026
• Pearson IAL Computer Science Unit 2 Programming Language Subset (PLS), Python 3
• Pearson IAL Computer Science IAS sample assessment materials (Unit 2 paper and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.