Sorting Algorithms | Bubble, Selection, Insertion Sort Complete Guide

Introduction

”Sorting is the Beginning of Algorithms”

Sorting is the most fundamental algorithm. It’s the best topic for learning time complexity analysis and optimization.

---

1. Bubble Sort

Algorithm

Compare adjacent elements and move larger values to the right:

[5, 2, 4, 1, 3]
 ↓ Compare & swap
[2, 5, 4, 1, 3]
    ↓
[2, 4, 5, 1, 3]
       ↓
[2, 4, 1, 5, 3]
          ↓
[2, 4, 1, 3, 5]  ← 5 in place

Python Implementation

Compare adjacent cells and swap if left is larger. Each pass “bubbles up” the largest value in the unsorted range to the right end.

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Already sorted if no swaps
        if not swapped:
            break
    
    return arr

# Test
arr = [5, 2, 4, 1, 3]
print(bubble_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

• Best: O(n) (already sorted)
• Average: O(n²)
• Worst: O(n²)
• Space: O(1)
• Stable: Yes

Step-by-Step Trace:

[5, 2, 4, 1, 3]

Pass 1:
[2, 5, 4, 1, 3]
[2, 4, 5, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 3, 5] ← 5 in place

Pass 2:
[2, 4, 1, 3, 5]
[2, 1, 4, 3, 5]
[2, 1, 3, 4, 5] ← 4 in place

Pass 3:
[1, 2, 3, 4, 5] ← 3 in place

Pass 4: No swaps → Done

---

2. Selection Sort

Algorithm

Find minimum and swap with front:

[5, 2, 4, 1, 3]
 ↓ Find min: 1
[1, 2, 4, 5, 3]  ← 1 in place
    ↓ Find min: 2
[1, 2, 4, 5, 3]  ← 2 in place
       ↓ Find min: 3
[1, 2, 3, 5, 4]  ← 3 in place
          ↓
[1, 2, 3, 4, 5]  ← Done

Python Implementation

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        # Find minimum after i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# Test
arr = [5, 2, 4, 1, 3]
print(selection_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

• Best: O(n²)
• Average: O(n²)
• Worst: O(n²)
• Space: O(1)
• Stable: No

Why Not Stable?

[5a, 5b, 2]

Step 1: Find min (2), swap with 5a
[2, 5b, 5a]  ← 5b now before 5a (order changed!)

Selection sort can change relative order of equal elements

---

3. Insertion Sort

Algorithm

Insert into sorted portion:

[5, 2, 4, 1, 3]
[5] 2 4 1 3  ← 5 is sorted
[2, 5] 4 1 3  ← Insert 2
[2, 4, 5] 1 3  ← Insert 4
[1, 2, 4, 5] 3  ← Insert 1
[1, 2, 3, 4, 5]  ← Insert 3

Python Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Move elements larger than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

# Test
arr = [5, 2, 4, 1, 3]
print(insertion_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

• Best: O(n) (already sorted)
• Average: O(n²)
• Worst: O(n²)
• Space: O(1)
• Stable: Yes

Step-by-Step Trace:

[5, 2, 4, 1, 3]

i=1, key=2:
  [5, 5, 4, 1, 3]  (shift 5)
  [2, 5, 4, 1, 3]  (insert 2)

i=2, key=4:
  [2, 5, 5, 1, 3]  (shift 5)
  [2, 4, 5, 1, 3]  (insert 4)

i=3, key=1:
  [2, 4, 5, 5, 3]  (shift 5)
  [2, 4, 4, 5, 3]  (shift 4)
  [2, 2, 4, 5, 3]  (shift 2)
  [1, 2, 4, 5, 3]  (insert 1)

i=4, key=3:
  [1, 2, 4, 5, 5]  (shift 5)
  [1, 2, 4, 4, 5]  (shift 4)
  [1, 2, 3, 4, 5]  (insert 3)

---

4. Sorting Comparison

Algorithm	Best	Average	Worst	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No

When to Use Each

# Bubble Sort
# - Educational purposes
# - Nearly sorted arrays (with early termination)

# Selection Sort
# - Minimize number of swaps
# - Small arrays

# Insertion Sort
# - Nearly sorted arrays (best case O(n))
# - Small arrays
# - Online sorting (elements arrive one at a time)

# Quick/Merge/Heap Sort
# - Large arrays
# - Need O(n log n) performance

---

5. Python Built-in Sorting

sorted() vs sort()

# sorted(): Returns new list
arr = [5, 2, 4, 1, 3]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 4, 1, 3] (original preserved)
print(sorted_arr)  # [1, 2, 3, 4, 5]

# sort(): In-place sorting
arr = [5, 2, 4, 1, 3]
arr.sort()
print(arr)  # [1, 2, 3, 4, 5] (original modified)

# Reverse
arr.sort(reverse=True)
print(arr)  # [5, 4, 3, 2, 1]

# Custom key
students = [('Alice', 85), ('Bob', 90), ('Charlie', 80)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)  # [('Bob', 90), ('Alice', 85), ('Charlie', 80)]

Timsort (Python’s Default)

# Python uses Timsort (hybrid of merge + insertion)
# - Time: O(n log n) worst case
# - Space: O(n)
# - Stable: Yes
# - Optimized for real-world data

arr = [5, 2, 4, 1, 3]
arr.sort()  # Uses Timsort

---

Practical Tips

Coding Interview Tips

# ✅ Use built-in functions most of the time
arr.sort()  # Timsort (O(n log n))

# ✅ When stable sort needed
# Python sort() is stable

# ✅ Partial sorting
import heapq
arr = [5, 2, 4, 1, 3]
smallest_3 = heapq.nsmallest(3, arr)
print(smallest_3)  # [1, 2, 3]

Advanced Example: Stable Sort with Keys

When same scores must preserve original input order, need stable sort like insertion, merge, or Timsort. Below is a pattern for sorting by (score descending, original index ascending).

from dataclasses import dataclass

@dataclass
class Row:
    name: str
    score: int

rows = [
    Row("A", 90),
    Row("B", 90),
    Row("C", 80),
]

# Python's sort is stable, so use index as secondary key
indexed = list(enumerate(rows))
indexed.sort(key=lambda t: (-t[1].score, t[0]))
ordered = [r for _, r in indexed]
print([r.name for r in ordered])  # ['A', 'B', 'C']

Common Mistakes

# ❌ Wrong: Comparing floats directly
# May cause unstable ordering

# ❌ Wrong: Using sorted() when in-place needed
# Doubles memory usage

# ❌ Wrong: Implementing O(n²) sort in contests
# Causes timeout (only when problem allows)

Cautions

• Partial sorting (top-k) may be more efficient with heap or heapq.nsmallest.
• For nearly sorted arrays, insertion sort or Timsort approaches best case.

In Practice

• In application code, use language built-in sorting and only define custom keys.
• For large-scale data, consider external sorting (disk, chunks) and distributed frameworks.

Comparison and Alternatives

Situation	Recommendation
General list sorting	list.sort / sorted
Top-k	Heap
Uniform integer distribution	Counting sort (separate article)

Additional Resources

• Python Sorting HOW TO
• CLRS — Introduction to Algorithms (sorting reference)

---

Summary

Key Points

1. Bubble: Adjacent swaps, O(n²), stable
2. Selection: Select minimum, O(n²), unstable
3. Insertion: Insert into sorted portion, O(n²), stable
4. Practice: Use Python sort() (Timsort)

Complexity Comparison

Sort	Best	Average	Worst	When to Use
Bubble	O(n)	O(n²)	O(n²)	Nearly sorted
Selection	O(n²)	O(n²)	O(n²)	Minimize swaps
Insertion	O(n)	O(n²)	O(n²)	Nearly sorted, small arrays

Next Steps

• Advanced Sorting (Quick/Merge/Heap)

---

Related Posts

• Sorting Problems | Coding Interview Sorting Patterns Complete Guide
• Binary Search | O(log n) Search Algorithm Complete Guide
• Algorithm Series Full Index

---

Keywords

Sorting Algorithm, Bubble Sort, Selection Sort, Insertion Sort, Time Complexity, Stable Sort, Coding Interview, Algorithm, O(n²), Timsort