Chapter 3: DSA Selection Sort
DSA Selection Sort – Let’s learn this together like I’m sitting next to you with a whiteboard, explaining slowly, step-by-step, with lots of visuals in words, real examples, and honest comments about when it’s actually useful.
What is Selection Sort?
Selection Sort is one of the simplest sorting algorithms — just like Bubble Sort.
Its main idea is very intuitive:
In every step, find the smallest element from the unsorted part of the array and swap it with the first unsorted position.
It’s called Selection Sort because in each pass we select the smallest (or largest) remaining element and put it in its correct position.
Think of it like this real-life analogy:
You have a row of students standing in random height order. You want to arrange them from shortest to tallest.
You do this:
- Look at all students → find the shortest one
- Ask that shortest student to come stand at position 1
- Now ignore position 1 → look at the remaining students → find the shortest among them
- Put that person in position 2
- Repeat until everyone is in correct position
That’s exactly how Selection Sort works!
Step-by-step example
Array: [64, 25, 12, 22, 11]
Goal: [11, 12, 22, 25, 64]
Pass 1 Find the smallest element in the whole array Smallest = 11 (at index 4)
Swap it with the first position (index 0)
After Pass 1: [11, 25, 12, 22, 64] ↑ sorted part
Pass 2 Now look only in the unsorted part: [25, 12, 22, 64] Smallest = 12 (at index 2)
Swap with the first unsorted position (index 1)
After Pass 2: [11, 12, 25, 22, 64] ↑ sorted part
Pass 3 Unsorted part: [25, 22, 64] Smallest = 22
Swap with position 2
After Pass 3: [11, 12, 22, 25, 64] ↑
Pass 4 Unsorted part: [25, 64] Smallest = 25 (already in correct place)
No swap needed
Pass 5 Only one element left → automatically sorted
Done!
Selection Sort – Visual Step-by-Step
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Initial: 64 25 12 22 11 Pass 1: → 11 25 12 22 64 (found 11, swapped with 64) Pass 2: → 11 12 25 22 64 (found 12, swapped with 25) Pass 3: → 11 12 22 25 64 (found 22, swapped with 25) Pass 4: → 11 12 22 25 64 (25 already correct) Pass 5: → 11 12 22 25 64 (done) |
Selection Sort Code (Python – very clean version)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
def selection_sort(arr): n = len(arr) # One by one move boundary of unsorted subarray for i in range(n): # Find the minimum element in unsorted part min_idx = i # Start from i+1 because 0 to i-1 is already sorted for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j # Swap the found minimum element with the first element of unsorted part arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr # Example numbers = [64, 25, 12, 22, 11] print("Before:", numbers) selection_sort(numbers) print("After: ", numbers) # Output: # Before: [64, 25, 12, 22, 11] # After: [11, 12, 22, 25, 64] |
Important – Time & Space Complexity (must remember for interviews)
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n²) | Even if already sorted, we still scan everything |
| Average Case | O(n²) | |
| Worst Case | O(n²) | Reverse sorted — worst possible |
| Space Complexity | O(1) | Only uses a few variables — in-place sorting |
Number of comparisons ≈ n²/2 (almost same in all cases)
Number of swaps ≈ n (very few swaps compared to Bubble Sort)
Selection Sort vs Bubble Sort – Quick Comparison
| Feature | Selection Sort | Bubble Sort |
|---|---|---|
| Best case time | O(n²) | O(n) with optimization |
| Worst case time | O(n²) | O(n²) |
| Number of swaps | Very few (~n) | Many (up to n²/2) |
| Best for | When swapping is expensive | When array is almost sorted |
| Intuitive logic | Find min and place it | Bubble largest to end |
| Stable? | No | Yes |
| Common in interviews? | Yes (explain + code) | Yes (but less than others) |
When is Selection Sort actually useful?
Almost never in real-world libraries — better algorithms exist.
But it is still taught and asked because:
- Extremely easy to understand and implement
- Fewer swaps than Bubble Sort (good when swapping is costly)
- Good teaching algorithm for in-place sorting concept
- Sometimes appears in interviews (especially for freshers)
- Helps you understand how greedy choice works (always pick current best)
Real sorting algorithms used in practice:
- Quick Sort
- Merge Sort
- Timsort (Python, Java)
- Introsort (C++)
Summary – Selection Sort in one line each
- In each step, find the smallest element in the unsorted part
- Swap it with the first position of the unsorted part
- Very simple logic
- Always takes O(n²) time — no early exit
- Very few swaps compared to Bubble Sort
- In-place and not stable
- Great for learning — almost never used in real code
Want to continue with the next simple sorting algorithm?
I can explain in the same style:
- Insertion Sort (actually very useful in practice)
- How Insertion Sort compares to Selection Sort and Bubble Sort
- Common interview questions that use similar logic
- When interviewers ask you to improve these simple sorts
Just tell me which topic you want next! 😄
