Bubble sort walks the row, swaps any two neighbors out of order, and repeats until a full pass makes no swap. It is slow but the rule is the clearest there is.
About 3 min of reading
Run bubble sort and count its work.
Sort a small row with bubble.
Before you run it, say out loud what it will print. Then open the answer.
Count swaps on a reversed row.
Before you run it, say out loud what it will print. Then open the answer.
Show an ordered row needs no swap.
Before you run it, say out loud what it will print. Then open the answer.
Print the rough cost of four items.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Bubble sort is the easiest rule to say and draw, so it is used to teach. Real code uses a built-in sort, which is far faster.
Each pass looks at every pair, and it may take many passes. For a thousand items that is a million steps, which is why it is only for small rows.
nums = [5, 3, 4, 1]
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)One pass moves the largest to the end. The big value bubbles right one step at a time.
def bubble(a):
changed = True
while changed:
changed = False
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
changed = True
return a
print(bubble([5, 3, 1]))Keep passing until a pass makes no swap. When nothing swaps, the row is ordered.
nums = [3, 2, 1]
swaps = 0
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
swaps += 1
print(swaps)Reversed rows need the most swaps. Each pair out of order is one swap.
nums = [1, 2, 3]
changed = False
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
changed = True
print(changed)A clean pass makes no swap, so the sort stops. Ordered input is the fast case.
nums = [9, 1]
nums[0], nums[1] = nums[1], nums[0]
print(nums)Bubble only ever swaps neighbors. A far-off value moves one step per pass.
print(len([1, 2, 3, 4]) ** 2)Roughly, a row of n items takes n squared steps. That is fine for small rows and bad for big ones.
rows = [[2, "a"], [2, "b"]]
print(rows[0] > rows[1])Equal items never swap, so they keep their order. Bubble sort is stable for that reason.
nums = [1, 2, 3]
changed = True
changed = False
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
changed = True
print(not changed)The flag is what lets a sort stop early on ordered data.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.