Sorting Algorithms
Implement Selection Sort, Bubble Sort, and Insertion Sort with complexity analysis.
Sorting Algorithms
Sorting is the process of arranging elements in a specific order. It is fundamental - many algorithms depend on sorted data.
Comparison of Basic Sorts
| Header | |||||
|---|---|---|---|---|---|
| Algorithm | Best | Average | Worst | Space | Stable? |
| Header | |||||
|---|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Selection Sort
Idea: Find the minimum, swap it to the front. Repeat.
``
[64, 25, 12, 22, 11]
^-- find min (11) → swap with 64
[11, 25, 12, 22, 64]
^-- find min (12) → swap with 25
[11, 12, 25, 22, 64]
^-- find min (22) → swap with 25
[11, 12, 22, 25, 64] ✓ Sorted
`
Always O(n²) - doesn't care about existing order.
Bubble Sort
Idea: Bubble larger elements to the end by repeatedly swapping adjacent pairs.
`
[5, 3, 8, 1, 2]
Pass 1: [3, 5, 1, 2, 8] (8 bubbles to end)
Pass 2: [3, 1, 2, 5, 8] (5 bubbles up)
Pass 3: [1, 2, 3, 5, 8] ✓ Sorted
`
Best case O(n) when already sorted (with early termination flag).
Insertion Sort
Idea: Build sorted portion one element at a time. Like sorting cards in hand.
`
[5, 3, 8, 1, 2]
Pick 3: [3, 5, 8, 1, 2] (insert 3 before 5)
Pick 8: [3, 5, 8, 1, 2] (8 already in place)
Pick 1: [1, 3, 5, 8, 2] (insert 1 at front)
Pick 2: [1, 2, 3, 5, 8] ✓ Sorted
``
Best case O(n) - excellent for nearly sorted data. Used in practice as the base case for Timsort (Python/Java default sort).Code Example
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
data = [64, 25, 12, 22, 11]
print("Selection:", selection_sort(data.copy()))
print("Bubble: ", bubble_sort(data.copy()))
print("Insertion:", insertion_sort(data.copy()))Practice Problems
- 01Sort an array of 0s, 1s, and 2s without using a sorting algorithm (Dutch National Flag)
- 02Find the kth largest element using selection sort logic
- 03Sort an almost-sorted array where each element is at most k positions from its sorted position