Selection Sort is a simple sorting algorithm that divides the input list into two parts:
- Sorted part
- Unsorted part
The algorithm repeatedly selects the smallest (or largest) element from the unsorted part and places it at the beginning of the sorted part.
This process continues until the entire list is sorted.
Here’s how the Selection Sort algorithm works:
- Start with an unsorted list of elements.
- Set the first element as the minimum (or maximum) value.
- Compare the minimum (or maximum) value with the next element in the list. If a smaller (or larger) element is found, update the minimum (or maximum) value to that element.
- Repeat step 3 for the remaining elements in the unsorted part of the list, updating the minimum (or maximum) value as necessary.
- Once you reach the end of the unsorted part, swap the minimum (or maximum) value with the first element of the unsorted part.
- Move the boundary of the sorted part one element to the right.
- Repeat steps 2-6 until the entire list is sorted.
Example:
Consider the following unsorted list of integers: [5, 3, 8, 2, 1].
Pass 1:
The minimum value is 1 (found at index 4). Swap it with the first element. The list becomes
[1, 3, 8, 2, 5].Pass 2:
The minimum value is 2 (found at index 3). Swap it with the second element. The list becomes
[1, 2, 8, 3, 5].Pass 3:
The minimum value is 3 (found at index 3). Since it is already in the correct position, no swap is needed. The list remains
[1, 2, 8, 3, 5].Pass 4:
The minimum value is 5 (found at index 4). Swap it with the fourth element. The list becomes
[1, 2, 3, 5, 8]Pass 5:
The minimum value is 8 (found at index 4). Since it is already in the correct position, no swap is needed. The list remains
[1, 2, 3, 5, 8].Selection Sort has a time complexity of O(n2) in the average and worst cases, where ‘n’ is the number of elements in the list.
Similar to Bubble Sort, it is not considered efficient for large lists but can be useful for small lists or partially sorted lists.