🎯 Selection Sort

Beginner ~12 min read

Bubble Sort swaps elements repeatedly. What if swaps are expensive? Selection Sort finds the minimum element and swaps it once per pass - much fewer swaps! Let's see how.

How Selection Sort Works

Selection Sort divides the array into sorted and unsorted portions. It repeatedly selects the minimum element from the unsorted portion and places it at the end of the sorted portion.

The Algorithm

Find the minimum element in the unsorted portion
Swap it with the first element of the unsorted portion
Move the boundary between sorted and unsorted
Repeat until the entire array is sorted

Key difference from Bubble Sort: Only one swap per pass!

See It in Action

Watch how Selection Sort finds the minimum and swaps it once per pass:

Color Legend

🔵 Blue: Unsorted elements
🟣 Purple: Searching for minimum
🔴 Pink: Current minimum found
🟡 Yellow: Comparing elements
🟠 Orange: Swapping
🟢 Green: Sorted (in final position)

The Code

# Selection Sort - Basic Implementation
# Find minimum and swap - reduces number of swaps

def selection_sort(arr):
    """Selection Sort - O(n²) but fewer swaps than Bubble Sort"""
    n = len(arr)
    
    print(f"Sorting: {arr}\n")
    
    # Track swaps
    swaps = 0
    comparisons = 0
    
    for i in range(n - 1):
        # Find minimum in unsorted portion
        min_idx = i
        print(f"Pass {i + 1}: Finding minimum from index {i}...")
        
        for j in range(i + 1, n):
            comparisons += 1
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap if needed
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swaps += 1
            print(f"  Swapped {arr[min_idx]} and {arr[i]}: {arr}")
        else:
            print(f"  {arr[i]} already in correct position")
        
        print(f"  After pass {i + 1}: {arr}\n")
    
    print(f"Final sorted: {arr}")
    print(f"\nStats:")
    print(f"  Comparisons: {comparisons}")
    print(f"  Swaps: {swaps}")
    return arr

# Test
numbers = [64, 25, 12, 22, 11]
result = selection_sort(numbers.copy())

print("\n=== Key Insight ===")
print("Selection Sort makes fewer swaps than Bubble Sort!")
print("Bubble Sort: O(n²) swaps")
print("Selection Sort: O(n) swaps (at most n-1)")

Output

Click Run to execute your code

Why "Selection"? Because we select the minimum element in each pass!

Quick Quiz

How many swaps does Selection Sort make for an array of size n?

Show answer
At most n-1 swaps (one per pass). Bubble Sort can make up to n(n-1)/2 swaps!
Is Selection Sort faster than Bubble Sort?

Show answer
Both are O(n²) for comparisons. But Selection Sort makes fewer swaps, so it's faster when swaps are expensive (e.g., swapping large objects).

Bubble Sort vs Selection Sort: Complete Comparison

Both are O(n²) algorithms, but they have different strengths. Let's see the difference in action:

# Selection Sort vs Bubble Sort
# Compare the two algorithms

def bubble_sort(arr):
    """Bubble Sort for comparison"""
    arr = arr.copy()
    n = len(arr)
    swaps = 0
    comparisons = 0
    
    for i in range(n - 1):
        for j in range(n - i - 1):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swaps += 1
    
    return arr, swaps, comparisons

def selection_sort(arr):
    """Selection Sort for comparison"""
    arr = arr.copy()
    n = len(arr)
    swaps = 0
    comparisons = 0
    
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            comparisons += 1
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swaps += 1
    
    return arr, swaps, comparisons

# Test with same array
test_array = [64, 25, 12, 22, 11, 90, 88, 45, 50, 33]

print("=== Comparison: Bubble Sort vs Selection Sort ===\n")
print(f"Array: {test_array}\n")

# Bubble Sort
result1, swaps1, comps1 = bubble_sort(test_array)
print("Bubble Sort:")
print(f"  Sorted: {result1}")
print(f"  Swaps: {swaps1}")
print(f"  Comparisons: {comps1}\n")

# Selection Sort
result2, swaps2, comps2 = selection_sort(test_array)
print("Selection Sort:")
print(f"  Sorted: {result2}")
print(f"  Swaps: {swaps2}")
print(f"  Comparisons: {comps2}\n")

print("=== Analysis ===")
print(f"Swap reduction: {swaps1 - swaps2} fewer swaps!")
print(f"Comparisons: Same O(n²) for both")
print("\n✅ Selection Sort wins when swaps are expensive!")
print("❌ Both are still O(n²) - use for small arrays only")

Output

Click Run to execute your code

Performance Comparison

Metric	Bubble Sort	Selection Sort	Winner
Comparisons	O(n²)	O(n²)	Tie
Swaps	O(n²)	O(n)	✅ Selection Sort
Best Case	O(n) with flag	O(n²) always	✅ Bubble Sort
Worst Case	O(n²)	O(n²)	Tie
Stable	Yes	No	✅ Bubble Sort
Space	O(1)	O(1)	Tie

Pros & Cons

🫧 Bubble Sort

✅ Pros

Adaptive: O(n) on sorted data
Stable: Preserves order of equal elements
Simple: Easy to understand
Early exit: Can detect sorted array

❌ Cons

Many swaps: O(n²) swaps
Slow: Lots of element movement
Not practical: Rarely used in production

🎯 Selection Sort

✅ Pros

Fewer swaps: Only O(n) swaps
Predictable: Always same number of comparisons
Good for expensive swaps: Minimizes writes
Simple: Easy to implement

❌ Cons

Not adaptive: Always O(n²)
Not stable: Can change order of equals
No early exit: Can't detect sorted array

When to Use Which?

🫧 Choose Bubble Sort When:

✅ Array might be nearly sorted (can exit early)
✅ You need stable sorting (preserve order of equal elements)
✅ Learning sorting algorithms (simplest to understand)
✅ Swaps are cheap, comparisons are expensive

Example: Sorting a list that's already 90% sorted - Bubble Sort will finish in ~O(n) time!

🎯 Choose Selection Sort When:

✅ Swaps are expensive (e.g., swapping large objects, database records)
✅ Memory writes are costly (embedded systems, flash memory)
✅ You want predictable performance (always same comparisons)
✅ Stability is not required

Example: Sorting large objects where each swap is expensive - Selection Sort minimizes swaps!

💡 Real-World Scenario

Sorting 1000 student records by grade:

If records are small (just numbers): Use Bubble Sort with optimization - might exit early if data is nearly sorted
If records are large (full student objects): Use Selection Sort - only ~1000 swaps instead of ~500,000!
If you need to preserve order of students with same grade: Use Bubble Sort (stable)
Best choice for production: Neither! Use Quick Sort or Merge Sort (O(n log n))

Complexity Analysis

Case	Time	Why
Best	O(n²)	Always scans entire unsorted portion
Average	O(n²)	Nested loops
Worst	O(n²)	No early exit possible
Space	O(1)	In-place sorting

⚠️ No Optimization

Unlike Bubble Sort, Selection Sort cannot exit early even if the array is already sorted. It always makes O(n²) comparisons.

When to Use Selection Sort

✅ Use When:

Swaps are expensive (e.g., swapping large objects)
Memory writes are costly
Array is small (< 100 elements)
Simplicity matters

❌ Avoid When:

Array is large (O(n²) is too slow)
Need stable sorting
Array might be nearly sorted
Better alternatives available

Common Misconceptions

❌ Misconception 1: "Selection Sort is faster than Bubble Sort"

Reality: Both are O(n²) for comparisons. Selection Sort only wins when swaps are expensive.

✅ Correct: "Selection Sort makes fewer swaps (O(n) vs O(n²))"
✅ Correct: "Selection Sort is better when swapping is costly"
❌ Wrong: "Selection Sort is always faster" - Not true! Same time complexity.

❌ Misconception 2: "Selection Sort can be optimized like Bubble Sort"

Reality: Selection Sort cannot detect if the array is already sorted and exit early.

✅ Bubble Sort: Can use a flag to detect no swaps → exit early → O(n) best case
❌ Selection Sort: Must always find minimum in each pass → Always O(n²)
Why? Selection Sort doesn't know if elements are in order until it checks all of them

❌ Misconception 3: "Fewer swaps means Selection Sort is stable"

Reality: Selection Sort is NOT stable - it can change the relative order of equal elements.

Example: Sorting [4a, 2, 4b, 1] by value:

Selection Sort: [1, 2, 4b, 4a] ❌ - Order of 4a and 4b changed!
Bubble Sort: [1, 2, 4a, 4b] ✅ - Order preserved
Why? Selection Sort swaps distant elements, which can jump over equal values

❌ Misconception 4: "Selection Sort is good for nearly sorted data"

Reality: Selection Sort performs the same regardless of initial order!

❌ Selection Sort: Always O(n²) - doesn't matter if data is sorted or not
✅ Bubble Sort: O(n) on sorted data, O(n²) on random data
✅ Insertion Sort: O(n) on nearly sorted data - BEST choice for this case!

❌ Misconception 5: "Use Selection Sort for production code"

Reality: Both Bubble and Selection Sort are O(n²) - too slow for real applications!

For small arrays (< 50): Use Insertion Sort (O(n²) but faster in practice)
For general use: Use Quick Sort or Merge Sort (O(n log n))
For nearly sorted: Use Insertion Sort (O(n) best case)
Selection Sort? Only when swaps are extremely expensive (rare!)

💡 Key Takeaway

Selection Sort is a teaching tool to understand:

✅ Trade-off between comparisons and swaps
✅ Why stability matters
✅ Why adaptivity is valuable
✅ When O(n) swaps beats O(n²) swaps

In practice? Use better algorithms! Selection Sort teaches concepts, not production techniques.

Summary

The 3-Point Selection Sort Guide

Pattern: Find minimum, swap once per pass
Advantage: O(n) swaps vs O(n²) for Bubble Sort
Limitation: Always O(n²) comparisons, not stable

Interview tip: Mention Selection Sort when asked about minimizing swaps!

What's Next?

Selection Sort improves on swaps, but we can do better! Next: Insertion Sort - works great on nearly sorted data and is stable!

Practice: Try implementing Selection Sort to find the maximum instead of minimum (sorts in descending order)!

Previous Bubble Sort

Next Insertion Sort

How Selection Sort Works

The Algorithm

See It in Action

Color Legend

The Code

Quick Quiz

Bubble Sort vs Selection Sort: Complete Comparison

Performance Comparison

Pros & Cons

🫧 Bubble Sort

✅ Pros

❌ Cons

🎯 Selection Sort

✅ Pros

❌ Cons

When to Use Which?

🫧 Choose Bubble Sort When:

🎯 Choose Selection Sort When:

💡 Real-World Scenario

Complexity Analysis

⚠️ No Optimization

When to Use Selection Sort

✅ Use When:

❌ Avoid When:

Common Misconceptions

❌ Misconception 1: "Selection Sort is faster than Bubble Sort"

❌ Misconception 2: "Selection Sort can be optimized like Bubble Sort"

❌ Misconception 3: "Fewer swaps means Selection Sort is stable"

❌ Misconception 4: "Selection Sort is good for nearly sorted data"

❌ Misconception 5: "Use Selection Sort for production code"

💡 Key Takeaway

Summary

The 3-Point Selection Sort Guide

What's Next?

Enjoying these tutorials?