Selection Sort
Problem
Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.
Examples:
Example 1:
Input: arr = [64, 25, 12, 22, 11]
Output: [11, 12, 22, 25, 64]
Explanation: The algorithm repeatedly finds the minimum element and puts it at the beginning.
Example 2:
Input: arr = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: The algorithm sorts the array by selecting the minimum element in each pass.
Solution
Intuition
- Selection Sort divides the input array into two parts: a sorted subarray and an unsorted subarray.
- Initially, the sorted subarray is empty and the unsorted subarray is the entire input array.
- The algorithm repeatedly selects the smallest element from the unsorted subarray and moves it to the end of the sorted subarray.
- This process continues until the entire array is sorted.
Approach
- Find the minimum element in the unsorted array.
- Swap it with the first element of the unsorted part.
- Move the boundary between the sorted and unsorted subarrays one element to the right.
- Repeat until the entire array is sorted.
Complexity Analysis
- Time Complexity: O(n²) for all cases (best, average, and worst) because the algorithm always makes n(n-1)/2 comparisons.
- Space Complexity: O(1) as it only requires a single additional memory space for the temporary variable used in swapping.
Implementation
CPP
Run your code to see output here