Iterative Sorting — Bubble, Selection & Insertion
Deep dive into the three classic O(n²) sorts: pseudocode, complexity analysis, stability, adaptivity, and comparative breakdown — with hands‑on DSA problems.
📌 Core Topic: Iterative sorting forms the foundation of algorithm design. Understanding these three O(n²) sorts is essential for DSA interviews and building intuition for more advanced algorithms like Merge Sort and Quick Sort.
🎯 What you'll learn: How each algorithm works step‑by‑step, its pseudocode, time/space complexity, stability, adaptivity, and common DSA questions that use them.
Bubble Sort
Selection Sort
Insertion Sort
1 Bubble Sort StableAdaptive
How it works: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed. Larger elements "bubble" toward the end of the list.
Optimization: The swapped flag stops early if already sorted – makes it adaptive.
Complexity Analysis
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best (already sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (reverse sorted) | O(n²) | O(1) |
Stability: ✅ Stable – equal elements maintain their relative order.
Adaptivity: ✅ Adaptive – performs better on partially sorted data.
2 Selection Sort Unstable
How it works: Divides the input into a sorted and an unsorted region. It repeatedly selects the smallest element from the unsorted region and moves it to the end of the sorted region.
Always performs O(n²) comparisons, but only O(n) swaps — useful when writes are expensive.
Complexity Analysis
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best | O(n²) | O(1) |
| Average | O(n²) | O(1) |
| Worst | O(n²) | O(1) |
Stability: ❌ Unstable – swapping can change relative order of equal elements.
Adaptivity: ❌ Not adaptive – always O(n²) comparisons.
3 Insertion Sort StableAdaptive
How it works: Builds the final sorted array one item at a time. It picks each element from the unsorted part and inserts it into its correct position within the sorted part, shifting larger elements to the right.
Like sorting playing cards in your hand. Very efficient for small or nearly sorted data.
Complexity Analysis
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best (already sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (reverse sorted) | O(n²) | O(1) |
Stability: ✅ Stable – equal keys maintain order.
Adaptivity: ✅ Adaptive – very fast on nearly sorted data.
Comparative Analysis
All three algorithms have O(n²) average time complexity and O(1) auxiliary space – but their behaviour differs significantly.
| Property | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
| Best Time | O(n) | O(n²) | O(n) |
| Average Time | O(n²) | O(n²) | O(n²) |
| Worst Time | O(n²) | O(n²) | O(n²) |
| Space | O(1) | O(1) | O(1) |
| Stable | ✅ Yes | ❌ No | ✅ Yes |
| Adaptive | ✅ Yes | ❌ No | ✅ Yes |
| Swaps (Worst) | O(n²) | O(n) | O(n²) (shifts) |
| Best Use Case | Nearly sorted, small data | Minimal writes needed | Small or online data |
Verdict: In practice, Insertion Sort outperforms both for small N or partially sorted data. Bubble Sort is rarely used except for teaching. Selection Sort has niche applications where write cost is high.
DSA Questions & Drills
Sharpen your understanding with these problems that directly use or modify the three sorting algorithms.
🔰 Beginner Level
1. Count Swaps in Bubble Sort
Problem: Given an array, sort it using Bubble Sort and return the total number of swaps performed. (Useful for array inversion count approximation.)
def bubble_swap_count(arr):
n = len(arr)
swaps = 0
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return swaps, arr2. Selection Sort on a List of Tuples (by second element)
Problem: Adapt Selection Sort to sort a list of (name, age) tuples in ascending order of age.
def selection_by_age(people):
n = len(people)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if people[j][1] < people[min_idx][1]:
min_idx = j
people[i], people[min_idx] = people[min_idx], people[i]
return people(Note: Selection Sort is unstable, so equal ages may change order.)
3. Insertion Sort on a Nearly Sorted Array
Problem: Write a function that takes an array where each element is at most K positions away from its sorted position. Use Insertion Sort to sort it in O(nK) time.
def insertion_sort_k(arr, k):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= max(0, i-k) and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr⚡ Intermediate Level
4. Cocktail Shaker Sort (Bidirectional Bubble Sort)
Problem: Implement a variant of Bubble Sort that passes alternately from left to right and then right to left.
def cocktail_sort(arr):
n = len(arr)
swapped = True
start, end = 0, n-1
while swapped:
swapped = False
for i in range(start, end):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = True
if not swapped: break
swapped = False
end -= 1
for i in range(end-1, start-1, -1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = True
start += 1
return arr5. Use Insertion Sort to Find the Kth Smallest Element
Problem: Instead of fully sorting, stop Insertion Sort after K elements have been placed correctly. Return the Kth element.
def kth_smallest_insertion(arr, k):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
if i >= k-1 and i == k-1:
return arr[k-1]
return arr[k-1]Unsolved Practice
Test yourself: apply the concepts without looking at solutions.
1. Bubble Sort with Early Termination (adaptive)
Problem: Implement Bubble Sort that counts the number of passes actually executed and prints it. Compare with worst‑case passes.
2. Selection Sort in Descending Order
Problem: Modify Selection Sort to sort the array in descending order by selecting the maximum element instead of the minimum.
3. Check Sortedness with One Pass
Problem: Write a function that returns True if a given list is already sorted (non‑decreasing). Derive it from the insertion sort logic (without actually sorting).