← All lessons

Bubble sort

Sign in · Sign up

Lesson 12.3

Bubble sort compares neighbours and swaps them until the list is in order:

def bubble_sort(numbers):
    a = numbers.copy()
    n = len(a)
    for i in range(n):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                ...               # swap the neighbours
    return a
  • a = numbers.copy() — so the list you were given stays intact;
  • the inner loop goes up to n - 1 - i: after every pass the biggest item is already at the end, and it can be left alone;
  • a[j], a[j + 1] = a[j + 1], a[j] swaps the neighbours in one step;
  • range(n) in the inner loop goes out of bounds — a[j + 1] does not exist.

The check gives the list numbers. Write bubble_sort and print the sorted list — the original must stay as it was.

Hint

The outer loop makes passes, the inner one compares neighbours.

The inner one goes up to n - 1 - i: after every pass the biggest item is already at the end. Sort a copy (numbers.copy()), otherwise the original list gets spoiled.