Why Sorting Matters, and Bubble Sort

Why sort?

Sorted data is much easier to work with: binary search needs it, duplicates end up next to each other, and the smallest and largest items are at the ends. That's why sorting is one of the most studied problems in computing.

Bubble sort

Walk through the list comparing neighbours. If two are in the wrong order, swap them. After one pass, the biggest item has “bubbled up” to the end. Repeat.

Think of it like this: Lining up children by height: walk along the line and swap any two neighbours where the taller one is in front. After the first walk, the tallest child is at the end.

def bubble_sort(nums):
    n = len(nums)
    for done in range(n - 1):
        swapped = False
        for i in range(n - 1 - done):        # the last `done` items are already in place
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swapped = True
        print("after pass", done + 1, ":", nums)
        if not swapped:                      # nothing moved: already sorted
            break
    return nums

bubble_sort([5, 1, 4, 2, 8])

Output

after pass 1 : [1, 4, 2, 5, 8]
after pass 2 : [1, 2, 4, 5, 8]
after pass 3 : [1, 2, 4, 5, 8]

Tip: Bubble sort is easy to understand but slow. You'll almost never use it for real – it's here to teach the idea.