An integer array arr is given. Rearrange all values in non-decreasing order by applying the selection sort algorithm.
During every pass, the smallest value from the unsorted part must be selected and placed at the first position of the same part. Return the sorted array.
Example 1
Input: arr = [29, 10, 14, 37, 13]
Output: [10, 13, 14, 29, 37]
Explanation: Value 10 is selected first, followed by 13, 14, and 29. Every selected value is placed at the next boundary of the sorted part.
Example 2
Input: arr = [7]
Output: [7]
Explanation: A single value already occupies the correct position, so no pass or swap is required.
Approach
Selection sort divides an array into a sorted prefix and an unsorted suffix. Initially, the sorted prefix is empty. During every pass, a complete scan of the unsorted suffix locates the smallest remaining value.
The smallest remaining value belongs at the first position of the unsorted suffix. A swap places the selected value at the boundary, and the sorted prefix grows by one position. Earlier sorted positions never need another change.
Algorithm
The array length
nis stored so the sorted and unsorted regions can be tracked by index.Every boundary index from
0throughn - 2is visited, and the boundary is treated as the next position requiring the correct value.An index named
minIndexis initialized with the current boundary because the boundary value is the first minimum candidate.The remaining unsorted suffix is scanned from
boundary + 1throughn - 1so every possible smaller value is examined.minIndexis updated whenever a value smaller than the current minimum candidate is found.The selected minimum is exchanged with the boundary value when both positions differ, so an unnecessary self-swap is avoided.
The sorted array is returned after every required boundary has been processed.
Dry Run
Selection Sort Image
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts an integer array with repeated minimum selection. vector<int> selectionSort(vector<int>& arr) { int n = arr.size(); // Every pass fixes one boundary position in the sorted prefix. for (int boundary = 0; boundary < n - 1; boundary++) { int minIndex = boundary; // The unsorted suffix is scanned for the smallest remaining value. for (int current = boundary + 1; current < n; current++) { // A smaller value becomes the new minimum candidate. if (arr[current] < arr[minIndex]) { minIndex = current; } } // A different minimum position makes a swap necessary. if (minIndex != boundary) { swap(arr[boundary], arr[minIndex]); } } return arr; }};// Driver codeint main() { // Input array vector<int> arr = {29, 10, 14, 37, 13}; // Solution object creation Solution obj; // Result printing vector<int> answer = obj.selectionSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(n2) in the best, average, and worst cases. The exact comparison count is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2.
Space Complexity: O(1) auxiliary space, because only index and temporary variables are maintained. The input array is rearranged in place.
Interview follow-up Questions
No. A distant swap can reverse the original order of equal values. For labeled values [4a, 2, 4b, 1], the first swap produces [1, 2, 4b, 4a], so 4a moves behind 4b. Stable selection sort can be created by shifting intervening values instead of swapping, but extra writes are introduced.
Be the first to add a comment.