Overview
Selection Sort is a simple comparison-based sorting Algorithm. It works by dividing the list into two parts : – the sorted part at the end. Initially, the sorted part is empty and the unsorted part is the entire list. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted part and swaps it with the first element of the unsorted part.
Key Characteristics
- Time Complexity : – O(n²) for both average and worst case scenarios.
- Space Complexity : – O(1) (in place sorting).
- Stability : – Not Stable (may change the relative order of equal elements).
- Algorithm Type: – It is Comparison-Based Sorting.
How Selection Sort Works ???
- Divide the List into sorted and unsorted parts: –
- Start with the first element as the current minimum.
- Compare this elements with the rest of the list to find the smallest element.
- Swap the smallest element with the first element of the unsorted part.
- Repeat the Process: –
- Move the boundary between the sorted and unsorted parts one element to the right.
- Find the smallest element in the unsorted part and swap it with the first unsorted element.
- Continue tis process until the entire list is sorted.
Steps and Example
Consider the following unsorted array: –
[ 5, 3, 8, 4, 2 ]- Pass 1: –
- Find the minimum element in [5, 3, 8, 4, 2] which is “2”.
- Swap “2” with the first element “5” -> [2, 3, 8, 4, 5]
- Pass 2: –
- Find the minimum element in [3, 8, 4, 5] which is “3”.
- Swap “3” with the second element “3” -> [2, 3, 8, 4, 5]
- Pass 3: –
- Find the minimum element in [8, 4, 5] which is “4”.
- Swap “4” with the third element “8” -> [2, 3, 4, 8, 5]
- Pass 4: –
- Find the minimum element in [8, 5] which is “5”.
- Swap “5” with the fourth element “8” -> [2, 3, 4, 5, 8]
- Pass 5: –
- The last element is already in its correct position.