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!
šļø Extra Practice ā Algorithm Reps
Sorting algorithms are the classic training ground. Write each one by hand ā that is how you learn to think in loops and swaps.
š
Task 5: Insertion Sort
Medium
Sort like you sort playing cards in your hand: take each card and slide it back until it sits in the right place. Write insertion_sort(items) and print the sorted version of [5, 2, 9, 1, 7].
[1, 2, 5, 7, 9]
def insertion_sort(items):
items = items[:]
for i in range(1, len(items)):
card = items[i]
j = i - 1
while j >= 0 and items[j] > card:
items[j + 1] = items[j]
j -= 1
items[j + 1] = card
return items
print(insertion_sort([5, 2, 9, 1, 7]))
ā
Task 6: Is It Sorted?
Easy
Write is_sorted(items) that returns True only when every item is less than or equal to the next one ā one pass, O(n). Print it for [1, 2, 3], [1, 3, 2] and [].
True
False
True
def is_sorted(items):
for i in range(len(items) - 1):
if items[i] > items[i + 1]:
return False
return True
print(is_sorted([1, 2, 3]))
print(is_sorted([1, 3, 2]))
print(is_sorted([]))
š
Task 7: Sort by a Rule
Medium
Python's sorted() takes a key telling it what to compare. Sort ["banana", "fig", "apple", "kiwi"] by length, then alphabetically, then by last letter (key=lambda w: w[-1]). Print all three lists.
You have players = [("Ana", 42), ("Ben", 91), ("Cy", 67)]. Print them sorted by score, highest first, one line each like Ben: 91. Hint: key=lambda p: p[1] with reverse=True.
Ben: 91
Cy: 67
Ana: 42
players = [("Ana", 42), ("Ben", 91), ("Cy", 67)]
for name, score in sorted(players, key=lambda p: p[1], reverse=True):
print(f"{name}: {score}")
š
Task 9: Full Merge Sort
Tricky
You already built the merge step ā now build the whole thing. merge_sort(items) splits the list in half, sorts each half by calling itself, then merges. Print the sorted version of [38, 27, 43, 3, 9, 82, 10].
[3, 9, 10, 27, 38, 43, 82]
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
return result + left[i:] + right[j:]
def merge_sort(items):
if len(items) <= 1:
return items
mid = len(items) // 2
return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
ā”
Task 10: Boss Level: Quicksort
Boss
The fastest of the classics. Pick the first item as the pivot, build a list of everything smaller and everything bigger, then quicksort those and join them: smaller + [pivot] + bigger. Print the sorted version of [7, 2, 9, 4, 1, 8, 3].
[1, 2, 3, 4, 7, 8, 9]
def quicksort(items):
if len(items) <= 1:
return items
pivot = items[0]
smaller = [x for x in items[1:] if x <= pivot]
bigger = [x for x in items[1:] if x > pivot]
return quicksort(smaller) + [pivot] + quicksort(bigger)
print(quicksort([7, 2, 9, 4, 1, 8, 3]))