Bubble Sort
Sorting: lesson 2 of 8
Swap neighbours until the big values float to the end.
Lesson 2 of 8 · 4 min
Bubble Sort
Step 1 of 27
compares0swaps0
a
b
4
1
5
2
6
3
Bubble sort only ever compares neighbours. Nothing may jump across the row.
The Idea
Compare each adjacent pair and swap them when they are out of order. After one pass the largest value has bubbled all the way to the end. Repeat, and the sorted region grows from the right, all at a cost of O(n²).
Real-World Example
A line of kids sorting themselves by height, but only allowed to trade places with whoever stands directly beside them. The tallest keeps getting nudged rightward until they reach the end of the line.
The Code
def bubble_sort(nums):
n = len(nums)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if nums[i] > nums[i + 1]: # out of order?
nums[i], nums[i + 1] = nums[i + 1], nums[i]
swapped = True
if not swapped: # already sorted
return nums
return nums
# bubble_sort([5, 1, 4, 2]) -> [1, 2, 4, 5]Your turn
Put the steps in the right order.
- Repeat passes until one completes with no swaps
- Compare that pair
- Start at the first adjacent pair
- Swap them if the left one is larger
Mini quiz
1 / 3