Selection Sort is a simple and intuitive sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, swapping it with the leftmost unsorted element (putting it in sorted order) and moving the sublist boundaries one element to the right.
Implementation of Selection Sort
// Time Complexity: O(n*n) (where n = size of the array)
// for the best, worst and average cases.
// Space Complexity: O(1)
void selectionSort(int arr[], int n)
{
for (int i = 0; i <= n - 2; i++)
{
int min = i;
for (int j = i; j <= n - 1; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
swap(arr[min], arr[i]);
}
}
Logic:
1. Outer Loop: Iterate from the start of the array to the second last element.
2. Initialize Minimum: Assume the current element is the smallest (min = i).
3. Inner Loop: Find the smallest element in the unsorted portion of the array.
Iterate through the remaining elements (
j = iton - 1).If a smaller element is found (
arr[j] < arr[min]), update the index of the smallest element (min = j).
4. Swap: Swap the found minimum element with the first unsorted element.
Time Complexity: O(n²)
Explanation: The outer loop runsn - 2i.e.n - 1times and the inner loop runs up ton - 1times, resulting in O(n²) for all (best, worst and average) cases.
Space Complexity: O(1)
Explanation: The algorithm sorts in place and uses a constant amount of extra space.
Example
Input: arr = [7, 5, 9, 2, 8], n = 5
Output: arr = [2, 5, 7, 8, 9]
Explanation: In each iteration, the smallest element from the unsorted portion of the array is selected and swapped with the first element of the unsorted portion. This process continues, reducing the unsorted portion of the array by one element each time, until the entire array is sorted.
Step-by-Step Explanation
Let's break down the steps for the example input arr = [7, 5, 9, 2, 8]:
1. Initial Array: [7, 5, 9, 2, 8]
2. Pass 1:
Array at the start of Pass 1:
[7, 5, 9, 2, 8]Find the minimum from index 0 to 4:
2Swap
2with the first element7Array after pass 1:
[2, 5, 9, 7, 8]
3. Pass 2:
Array at the start of Pass 2:
[2, 5, 9, 7, 8]Find the minimum from index 1 to 4:
5Swap
5with itself (no change).Array after pass 2:
[2, 5, 9, 7, 8]
4. Pass 3:
Array at the start of Pass 3:
[2, 5, 9, 7, 8]Find the minimum from index 2 to 4:
7Swap
7with9Array after pass 3:
[2, 5, 7, 9, 8]
5. Pass 4:
Array at the start of Pass 4:
[2, 5, 7, 9, 8]Find the minimum from index 3 to 4:
8Swap
8with9Array after pass 4:
[2, 5, 7, 8, 9]
6. Final Sorted Array:[2, 5, 7, 8, 9]
Visualization
Edge Cases
Already Sorted Array: The algorithm still performs O(n²) comparisons, making it inefficient for sorted inputs.
Array with Identical Elements: Handles duplicates correctly but doesn't provide any advantage over its time complexity.
Single Element Array: No swaps needed, the array remains unchanged.
Additional Notes
Inefficiency: Due to its O(n²) time complexity, Selection Sort is inefficient for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort.
Stability: Selection Sort is not stable, meaning it may change the relative order of elements with equal keys.
Use Case: Useful for small datasets or when memory space is limited since it sorts in place with O(1) additional space.
Conclusion
Selection Sort is a fundamental sorting algorithm that provides a clear introduction to the concept of sorting. Although not suitable for large datasets due to its quadratic time complexity, it is easy to understand and implement, making it an excellent teaching tool for learning about algorithmic concepts. Its simplicity and in-place sorting capability are its main advantages.