Selection Sort
Learn Selection Sort, a simple comparison-based sorting algorithm that divides the input list into a sorted and an unsorted region.
Ready to sort
Intuition
Imagine sorting a hand of cards. You scan the entire hand to find the smallest card, remove it, and place it at the front. Then you scan the remaining cards for the next smallest, and so on. This keeps the 'sorted pile' growing from left to right.
Concept
- Strategy: Repeatedly find the minimum element from the unsorted part and put it at the beginning.
- In-Place: Does not require extra memory proportional to input size (O(1) space).
- Unstable: Does not preserve the relative order of equal elements (by default).
How it Works
Algorithm:
- Start with the whole array as 'unsorted'.
- Iterate through the unsorted part.
- Find the index of the minimum element.
- Swap that minimum element with the first element of the unsorted part.
- Move the boundary of the sorted part one step to the right.
Step-by-Step Breakdown
Watch the visualization:
- Orange Bars: Elements being compared.
- Red Bar: Current minimum found in the pass.
- Green Bars: The growing sorted portion of the array.
Trace: [64, 25, 12, 22, 11]
Current Min is 64. Compare with 25. 25 < 64. New Min found!
Min: 25
Current Min is 25. Compare with 12. 12 < 25. New Min found!
Min: 12
Compare with 22. 22 > 12. Ignore.
Min: 12
Compare with 11. 11 < 12. New Min Found!
Final Min: 11
Swap Min (11) with Index 0 (64).
[11, 25, 12, 22, 64]
Element 11 is now sorted!
When to Use
- Small Files: Performs well on very small lists.
- Costly Writes: Minimizes the number of swaps (O(N) swaps), which is useful if writing to memory is expensive.
When NOT to Use
- Large Datasets: O(N²) time complexity makes it inefficient for large inputs.
- Nearly Sorted Data: Does not adapt to sorted data (still O(N²)).
How to Identify
"Find the smallest/largest K elements", "Minimize swaps".
Frequently Asked Questions
How does Selection Sort work?
Selection Sort works by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.
What is the time complexity of Selection Sort?
Selection Sort has a time complexity of O(n²) in all cases (worst, best, and average) because it always scans the entire unsorted list.
Is Selection Sort stable?
No, Selection Sort is not naturally stable because swaps can change the relative order of equal elements.