Bubble sort is one of the simplest sorting algorithms. It goes through a list again and again, compares two neighbouring items, and swaps them if they are in the wrong order. With each pass, the largest remaining item “bubbles up” to the end of the list. In this lesson you will write bubble sort in Python, trace it step by step, make it faster with a flag, and sort in descending order.

Run the code in our online Python compiler. The compiler does not take keyboard input, so the examples use fixed values.

 

How bubble sort works

  1. Start at the beginning of the list.
  2. Compare the first two items. If the first is larger, swap them.
  3. Move one step to the right, and compare the next pair.
  4. At the end of the pass, the largest item is in its final place at the end of the list.
  5. Repeat the passes, each time ignoring the items that are already in place, until the whole list is sorted.

 

Program: bubble sort in Python

def bubble_sort(items):
    a = items[:]            # work on a copy
    n = len(a)

    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

print(bubble_sort([5, 2, 9, 1, 5, 6]))

Output:

[1, 2, 5, 5, 6, 9]

The outer loop counts the passes. The inner loop compares the pairs. The range n – 1 – i gets shorter in every pass, because the last i items are already sorted. The line a[j], a[j + 1] = a[j + 1], a[j] swaps two items in one step. The copy (items[:]) keeps your original list unchanged.

 

Trace: the passes for [5, 2, 9, 1]

a = [5, 2, 9, 1]
n = len(a)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
    print('pass', i + 1, a)

Output:

pass 1 [2, 5, 1, 9]
pass 2 [2, 1, 5, 9]
pass 3 [1, 2, 5, 9]

Pass

What happens

List after the pass

1

9 bubbles to the end

[2, 5, 1, 9]

2

5 moves to its place

[2, 1, 5, 9]

3

2 and 1 are swapped

[1, 2, 5, 9]

A list of 4 items needs at most 3 passes.

 

Faster version: stop when there are no swaps

If a whole pass makes no swaps, the list is already sorted, and we can stop. A flag called swapped records this.

def bubble_sort_fast(items):
    a = items[:]
    n = len(a)
    passes = 0

    for i in range(n - 1):
        swapped = False
        passes += 1

        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True

        if not swapped:
            break

    return a, passes

print(bubble_sort_fast([1, 2, 3, 4, 5]))
print(bubble_sort_fast([5, 2, 9, 1]))

Output:

([1, 2, 3, 4, 5], 1)
([1, 2, 5, 9], 3)

The sorted list needs only one pass to find that nothing has to change. This improvement makes bubble sort fast on lists that are already sorted or nearly sorted.

 

Sort in descending order

Change the comparison from > to <:

def bubble_sort_desc(items):
    a = items[:]
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] < a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

print(bubble_sort_desc([5, 2, 9, 1]))

Output:

[9, 5, 2, 1]

Sort strings

The same program works for words, because Python can compare strings in alphabetical order.

print(bubble_sort(['pear', 'apple', 'fig']))
print(sorted(['pear', 'apple', 'fig']))

Output:

['apple', 'fig', 'pear']
['apple', 'fig', 'pear']

How fast is bubble sort?

Case

Time

Worst case (a list in reverse order)

About n × n comparisons, written O(n²)

Average case

O(n²)

Best case (already sorted, with the swapped flag)

O(n)

Bubble sort is easy to understand, but it is slow for large lists. For real programs, use Python’s built-in sorted() or the sort() method, which are far faster. Bubble sort is mainly for learning and exams.

 

Common mistakes

  • Looping to the wrong limit. The inner loop must stop at n – 1 – i. If it goes to n, you get an IndexError when you compare a[j + 1].
  • Forgetting to swap with the one-line assignment. Writing a[j] = a[j + 1] and then a[j + 1] = a[j] loses a value.
  • Changing the original list by accident. Work on a copy, or accept that the list changes.
  • Using < instead of >. That sorts in the opposite order.

 

Practice questions

  1. Sort [64, 34, 25, 12, 22, 11, 90] with bubble sort, and write the list after every pass.
  2. Count how many swaps the program makes for [5, 4, 3, 2, 1].
  3. Sort a list of words by their length.
  4. Change the program so that it sorts in descending order.
  5. Compare the time of bubble sort and sorted() on a list of 2,000 numbers.

FAQs

Why is it called bubble sort?

Because the larger items slowly move to the end of the list with each pass, like bubbles rising to the surface of water.

Is bubble sort stable?

Yes. Equal items keep their original order, because we swap only when the left item is strictly greater.

What is the best sorting method in Python?

For normal programs, use sorted() or list.sort(). They are much faster than bubble sort.

How many passes does bubble sort need?

At most n – 1 passes for a list of n items. The faster version can stop earlier.

PreviousNext