Sorting Algorithms¶
Three fundamental comparison sorts implemented from scratch, understanding their mechanics matters when reasoning about data preprocessing costs or why libraries choose specific algorithms under the hood.
Problem¶
Sort an array of integers in ascending order using:
- Bubble sort
- Insertion sort
- Selection sort
Approach¶
Bubble sort repeatedly swaps adjacent elements if they're out of order. After each pass, the largest unsorted element "bubbles" to its correct position.
Insertion sort builds the sorted array one element at a time. Pick the next element and shift larger elements right to make room. Works great on nearly-sorted data.
Selection sort finds the minimum element in the unsorted portion and swaps it into the next sorted position. Always makes O(n^2) comparisons regardless of input order.
Implementation¶
Bubble Sort¶
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1, 0, -1):
swapped = False
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
Insertion Sort¶
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i
while j > 0 and arr[j - 1] > key:
arr[j] = arr[j - 1]
j -= 1
arr[j] = key
Selection Sort¶
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
Complexity¶
| Algorithm | Time (best) | Time (avg/worst) | Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(1) | Yes |
| Insertion Sort | O(n) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(1) | No |
Takeaway¶
These O(n^2) sorts are rarely used on large datasets, but insertion sort is the go-to for small arrays, Python's Timsort switches to it below ~64 elements. Worth implementing once just to see why the O(n^2) bound matters less than you'd think on nearly-sorted data.