Bubble sort repeatedly walks the list, swapping neighbors that are out of order. Big values "bubble up" to the end. Easy to understand, but O(nĀ²) ā slow for big lists.
def bubble_sort(items):
n = len(items)
for i in range(n):
for j in range(n - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j] # swap
return items
š The Python swap trick
a, b = b, a swaps two values in one clean line ā no temporary variable needed!
šÆ Selection sort ā find the smallest
Selection sort finds the smallest item and puts it first, then the next smallest, and so on. Also O(nĀ²), but it makes fewer swaps.
def selection_sort(items):
n = len(items)
for i in range(n):
smallest = i
for j in range(i + 1, n):
if items[j] < items[smallest]:
smallest = j
items[i], items[smallest] = items[smallest], items[i]
return items
ā” Merge sort ā divide and conquer
Merge sort splits the list in half, sorts each half (recursively!), then merges the two sorted halves together. Much faster: O(n log n).
def merge_sort(items):
if len(items) <= 1: # base case
return items
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
š Comparing the sorts
Algorithm
Big-O
Idea
Bubble sort
O(nĀ²)
Swap neighbors
Selection sort
O(nĀ²)
Pick the smallest
Merge sort
O(n log n)
Split & merge
Python's .sort()
O(n log n)
Timsort (built-in)
š” In real life
You rarely write your own sort ā Python's sorted() and .sort() are highly optimized. But understanding how sorting works makes you a better problem-solver.
ā What you learned
Bubble & selection sort are simple but O(nĀ²).
Merge sort uses divide and conquer for O(n log n).
Swap values with a, b = b, a.
Real code uses Python's built-in sorted().
š® Time to Practice!
Sort it out ā from scratch! š
š«§
Task 1: Bubble Sort
Medium
Complete the swap inside bubble sort: if items[j] is bigger than items[j+1], swap them. Sorting [5, 2, 9, 1, 8] should print [1, 2, 5, 8, 9].
def bubble_sort(items):
n = len(items)
for i in range(n):
for j in range(n - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
return items
print(bubble_sort([5, 2, 9, 1, 8]))
šÆ
Task 2: Selection Sort
Tricky
Finish the inner loop that finds the index of the smallest remaining item. Sorting [15, 3, 10, 7] should print [3, 7, 10, 15].
def selection_sort(items):
n = len(items)
for i in range(n):
smallest = i
for j in range(i + 1, n):
if items[j] < items[smallest]:
smallest = j
items[i], items[smallest] = items[smallest], items[i]
return items
print(selection_sort([15, 3, 10, 7]))
š
Task 3: The Merge Step
Challenge
The heart of merge sort is merging two already sorted lists. Pick the smaller front item each time. Merge [1, 4, 8] and [2, 3, 6] ā [1, 2, 3, 4, 6, 8].
šļø
Task 4: Free Play ā Race the Built-in
Explore
Python's sorted() is the easy way. Try sorting numbers, words, and sorting in reverse. Experiment with reverse=True and sorting by length!