Selection Sort is another simple sorting algorithm. It works by repeatedly finding the minimum (or maximum, depending on sorting order) element from the unsorted part and putting it at the beginning.
How Selection Sort Works
Start with the first element as the minimum.
Search the entire unsorted part of the array to find the actual minimum element.
Swap the found minimum element with the first element.
Move the boundary of the sorted and unsorted part one step forward.
Repeat steps 1-4 until the whole array is sorted.
Example
Unsorted List: [5, 3, 8, 4, 2]
Letโs sort in ascending order step by step:
Pass 1:
Unsorted part: [5, 3, 8, 4, 2]
Find the minimum (2) among elements at index 0-4.
Swap it with the first element (5).
After swap: [2, 3, 8, 4, 5]
Pass 2:
Unsorted part: [3, 8, 4, 5] (index 1 to 4)
Find the minimum (3).
Swap it with the current first unsorted element (3โno real change).
After swap: [2, 3, 8, 4, 5]
Pass 3:
Unsorted part: [8, 4, 5] (index 2 to 4)
Find the minimum (4).
Swap it with 8.
After swap: [2, 3, 4, 8, 5]
Pass 4:
Unsorted part: [8, 5] (index 3 to 4)
Find the minimum (5).
Swap it with 8.
After swap: [2, 3, 4, 5, 8]
Now the list is sorted!
Key Points:
Time Complexity: O(nยฒ)
Number of swaps: At most (n-1) โ fewer than Bubble Sort
In-place sort (no extra space needed)
Not stable (can change the order of equal elements)
Simple to understand and implement, but not suitable for large lists
In summary: Selection Sort repeatedly selects the smallest (or largest) element from the unsorted section and swaps it with the first unsorted element, moving the sorted-portion boundary forward until complete.
