AI Hints
Home›DSA in Python Tutorial›Simple Sorts
DSA in Python · Lesson 50 of 132

Bubble Sort

Swap neighbours.

⏱ 2 min read▶ Video at 58:12🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Bubble sort is the simplest sorting algorithm to understand. Walk along the list, and whenever two neighbours are in the wrong order, swap them. After each pass, the biggest remaining item has bubbled up to the end.

Bubble Sort
From the video: Bubble Sort
  • Walk along the list
  • Swap neighbours in the wrong order
  • The biggest bubbles to the end

Watching the bubbles

The outer loop counts the passes. The inner loop compares each pair of neighbours, and swaps them if they're the wrong way round. Each pass can stop one place earlier, because the end is already sorted. We print the list after each pass. Run it. Watch nine bubble to the end first, then seven, then five.

bubble.pypython
def bubble_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
        print(f"pass {i + 1}: {nums}")
    return nums

bubble_sort([5, 2, 9, 1, 7])
Output
pass 1: [2, 5, 1, 7, 9]
pass 2: [2, 1, 5, 7, 9]
pass 3: [1, 2, 5, 7, 9]
pass 4: [1, 2, 5, 7, 9]

Bubble sort cost

There's a loop inside a loop, so bubble sort is O of N squared. That's fine for ten items, and hopeless for a million. It's mainly used for teaching. A small improvement is to stop early if a whole pass makes no swaps, because then the list is already sorted.

keyvalue
TimeO(n²)
SpaceO(1), in place
Best caseO(n) with early stop
Useteaching, tiny lists

Summary

Bubble sort swaps neighbours until the list is sorted. It's simple, but O of N squared. Next, selection sort.

Key takeaways
  • Compare neighbours
  • Swap if wrong
  • O(n²)
Next up: Selection Sort — pick the smallest each time