Bubble Sort and Insertion Sort
Code both quadratic sorting algorithms, understand why they are O(n²), and recognise the one case where insertion sort beats merge sort.
Why Study O(n²) Sorts?
Bubble sort and insertion sort are O(n²) in the worst case, making them impractical for large inputs. Yet every serious algorithm interview expects you to implement and analyse them. They teach fundamental concepts — comparison, swapping, stable sorting, and best-case behaviour — that apply to more advanced algorithms. Interviewers use them to test whether you can reason about loop invariants and asymptotic notation from first principles.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Bubble Sort: Bubble Up the Maximum
Bubble sort repeatedly scans the array and swaps adjacent elements that are out of order. After each full pass, the largest unsorted element 'bubbles up' to its final position at the end. After n-1 passes, the entire array is sorted. Its name comes from the way larger elements float upward like bubbles. It is the simplest sorting algorithm to describe but rarely used in practice.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()