Python Program for Bubble Sort
Beginner Searching and sorting Time O(n²) Space O(1)
Sorts a list by swapping neighbours that are out of order, pass after pass, and stops early once a pass makes no swaps.
Bubble sort is named after the way big items rise to the end of the list, like bubbles to the top of water. One pass
compares each pair of neighbours and swaps the pair when it's in the wrong order, which carries the largest item to the
end; the next pass carries the second largest to the place before it, and so on. Sorting [5, 1, 4], the first pass
swaps 5 and 1, then 5 and 4, giving [1, 4, 5]. It's slow on long lists, but most courses start with it because every
step can be followed by hand.
Program
def bubble_sort(items):
"""Sort items in place, from smallest to largest."""
n = len(items)
for i in range(n - 1):
swapped = False
# The last i items are already in their places
for j in range(n - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
break # a pass with no swaps: the list is sorted
numbers = [25, 12, 90, 11, 34, 22, 64]
print("Before:", numbers)
bubble_sort(numbers)
print("After: ", numbers)
Open in the editor Download bubble_sort.py
Output
Before: [25, 12, 90, 11, 34, 22, 64]
After: [11, 12, 22, 25, 34, 64, 90]
How it works
Step through the program line by line: each step below shows up as its line runs.
-
nis the number of items. The outer loop makes at most n − 1 passes: each pass puts one more item in its final place at the end, so once n − 1 of them are placed, the last one is too. -
swappedrecords whether this pass changes anything. It starts each pass asFalse. - The inner loop compares each item with its right-hand neighbour and swaps them when the left
one is bigger.
a, b = b, aswaps two values in one line (tuples). Each pass stopsiplaces before the end, because the lastiitems are already the largest, in order. - If a whole pass made no swaps, every neighbour is in order, so the list is sorted and
breakends the outer loop early. Without this check the function would always make all n − 1 passes, even on a list that is already sorted. - The program prints the list, sorts it, and prints it again.
bubble_sortchanges the list it's given, in place, and returns nothing, so the program printsnumbersitself after the call.
The list after each pass:
| Pass | List after the pass | Swaps |
|---|---|---|
| 1 | [12, 25, 11, 34, 22, 64, 90] | 5 |
| 2 | [12, 11, 25, 22, 34, 64, 90] | 2 |
| 3 | [11, 12, 22, 25, 34, 64, 90] | 2 |
| 4 | [11, 12, 22, 25, 34, 64, 90] | 0: sorted, so stop |
Pass 1 carries 90 from index 2 to the end. Pass 4 makes no swaps, so the function stops there, two passes before the 6 it could have made.
Time and space complexity
| Time | O(n²) |
|---|---|
| Extra space | O(1) |
Without the early stop, bubble sort always makes n − 1 passes and compares (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 pairs: 21 for 7 items, about half a million for 1,000. That's O(n²), the worst case, which a list in reverse order reaches. The early stop makes the best case O(n): an already sorted list takes one pass of n − 1 comparisons and no swaps. The sample list takes 4 passes and 18 comparisons. The sort happens inside the list with a few variables, so the extra space is O(1). Bubble sort is stable: it swaps only when the left item is strictly bigger, so equal items keep their order.
Other ways to write it
With a while loop
This version keeps making passes while the last one swapped something. It's shorter, but each pass goes to the end of the list, even over the items already in place there.
def bubble_sort(items):
swapped = True
while swapped:
swapped = False
for j in range(len(items) - 1):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
numbers = [25, 12, 90, 11, 34, 22, 64]
bubble_sort(numbers)
print(numbers)With Python's built-in sort
In real programs, use sorted(), which returns a new sorted list, or the list's sort() method, which sorts it in
place. Both take O(n log n) time and keep equal items in order.
numbers = [25, 12, 90, 11, 34, 22, 64] print(sorted(numbers)) numbers.sort(reverse=True) print(numbers)
Try it yourself
- Print the list at the end of each pass, to see the largest items settle at the end one by one.
- Sort a list that is already sorted and one in reverse order, and count the passes each one takes.
- Sort from largest to smallest by changing one character in the comparison.
- Sort a list of words, such as
["pear", "apple", "fig", "kiwi"]: strings compare in alphabetical order.