Selection Sort
Definition
Selection sort is a sorting algorithm that selects the smallest element from an unsorted part in each iteration and places that element at the beginning of the unsorted part.
Let us understand this algorithm with an analogy
Imagine a teacher organizing students in a morning assembly by height, from shortest to tallest.
Each time, the teacher starts by finding the shortest student from the unsorted line and placing them at the start of the unsorted line.
Then, the teacher looks at the remaining students, finds the next shortest, and lines them up behind the sorted line of students. This continues until all students are lined up from shortest to tallest.
This method is called Selection Sort because, in each step, the teacher "selects" the smallest student from the unsorted group and moves them to their correct position, sorting the group incrementally.
Let us understand a step-by-step working of Selection Sort with an example :
Suppose we have the following array of integers nums: [64, 34, 25, 10, 22, 11, 90] that we want to sort in ascending order:
Step-by-Step Working
Pass 1
- Current Position: Index 0 (value 64)
- Unsorted Portion: [64, 25, 12, 22, 11]
- Assumption: The minimum is initially the element at index 0, which is 64.
- Finding the Minimum:
- Compare 64 (at index 0) with 25 (at index 1). 25 is smaller, so update minIndex to 1.
- Compare 25 (at index 1) with 12 (at index 2). 12 is smaller, so update minIndex to 2.
- Compare 12 (at index 2) with 22 (at index 3). 12 is still smaller.
- Compare 12 (at index 2) with 11 (at index 4). 11 is smaller, so update minIndex to 4.
- Swapping:
- Swap the element at minIndex (index 4, value 11) with the element at the current position 0 (value 64).
Array after swapping:[11, 25, 12, 22, 64]
Pass 2
- Current Position: Index 1 (value 25)
- Unsorted Portion: [25, 12, 22, 64]
- Assumption: The minimum is initially the element at index 1, which is 25.
- Finding the Minimum:
- Compare 25 (at index 1) with 12 (at index 2). 12 is smaller, so update minIndex to 2.
- Compare 12 (at index 2) with 22 (at index 3). 12 is still smaller.
- Compare 12 (at index 2) with 64 (at index 4). 12 is still smaller.
- Swapping:
- Swap the element at minIndex (index 2, value 12) with the element at the current position 1 (value 25).
Array after swapping:[11, 12, 25, 22, 64]
Pass 3
- Current Position: Index 2 (value 25)
- Unsorted Portion: [25, 22, 64]
- Assumption: The minimum is initially the element at index 2, which is 25.
- Finding the Minimum:
- Compare 25 (at index 2) with 22 (at index 3). 22 is smaller, so update minIndex to 3.
- Compare 22 (at index 3) with 64 (at index 4). 22 is still smaller.
- Swapping:
- Swap the element at minIndex (index 3, value 22) with the element at the current position 2 (value 25).
Array after swapping: [11, 12, 22, 25, 64]
Pass 4
- Current Position: Index 3 (value 25)
- Unsorted Portion: [25, 64]
- Assumption: The minimum is initially the element at index 3, which is 25.
- Finding the Minimum:
- The only element left in the unsorted portion is 64 (at index 4), which is larger than 25.
- Swapping:
- Since 25 is already in the correct position, no swapping is needed.
Array remains: [11, 12, 22, 25, 64]
Do we need any more passes?
We have already done 4 passes, which means 4 out of 5 elements are at the right places. Imagine there are 10 seats in a bus and 10 passengers. 9 took their right seat, so automatically the last person would get the right seat without even searching for it. Since the n-1 elements are in their correct position then the remaining element will automatically go to the correct position. Therefore the array becomes sorted.
Final Sorted Array
After completing all passes, the array is now sorted in ascending order : [11, 12, 22, 25, 64].
Let's understand it through visuals
Here is the code of Selection sort in all languages:
Code in All Languages
C++ Code Try on Compiler!
class Solution
{
public:
void selectionSort(vector<int> &nums)
{
int n = nums.size();
for (int i = 0; i < n - 1; i++)
{
// Assume the current position is the minimum
int minIndex = i;
// Find the minimum element in the remaining unsorted portion
for (int j = i + 1; j < n; j++)
{
// Update minIndex if a smaller element is found
if (nums[j] < nums[minIndex])
{
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted portion
if (minIndex != i)
{
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
};
Java Code Try on Compiler!
class Solution {
void selectionSort(int[] nums) {
// Get the number of elements in the array
int n = nums.length;
// Traverse through all array elements except the last one
for (int i = 0; i < n - 1; i++) {
// Assume the current position is the minimum
int minIndex = i;
// Find the minimum element in the remaining unsorted portion
for (int j = i + 1; j < n; j++) {
// Update minIndex if a smaller element is found
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted portion
if (minIndex != i) {
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
}
Python Code Try on Compiler!
class Solution:
def selection_sort(nums):
# Traverse through all array elements except the last one
for i in range(len(nums) - 1):
# Assume the current position is the minimum
min_index = i
# Find the minimum element in the remaining unsorted portion
for j in range(i + 1, len(nums)):
# Update min_index if a smaller element is found
if nums[j] < nums[min_index]:
min_index = j
# Swap the found minimum element with the first element of the unsorted portion
if min_index != i:
nums[i], nums[min_index] = nums[min_index], nums[i]Javascript Code Try on Compiler!
class Solution {
selectionSort(nums) {
for (let i = 0; i < nums.length - 1; i++) {
// Assume the current position is the minimum
let minIndex = i;
// Find the minimum element in the remaining unsorted portion
for (let j = i + 1; j < nums.length; j++) {
// Update minIndex if a smaller element is found
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted portion
if (minIndex !== i) {
let temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
}Time Complexity
For an array with n elements, Selection Sort finds the minimum element from the unsorted portion in each iteration. During each pass, it compares the current element with all remaining unsorted elements :
- First Pass: n-1 comparisons
- Second Pass: n-2 comparisons
- Third Pass: n-3 comparisons
- ...
- Last Pass: 1 comparison
The total number of comparisons made is the sum of the first n-1 natural numbers, which is given by the formula: (n*(n−1))/2.
Simplifying this results in approximately (n*(n−1))/2, which is O(n²).
Number of Swaps: Each pass may involve a single swap operation, as only one element is placed in its final position per pass. Thus, the number of swaps is proportional to n, making it less compared to the number of comparisons.
Since in every pass, we need to compare between the elements and the number of comparisons does not decrease. It does not matter whether the array is already sorted, or the element is present in random order.
Therefore the time complexity in each of the Worst case, Average case, and best case is O(n²).
Space Complexity
Selection Sort has a constant space complexity of O(1). It only requires a small, fixed amount of extra space beyond the input array.
This additional space is used for a few variables:
Index Variables: To keep track of the current position and the index of the minimum element found.
Temporary Variable: For swapping elements within the array.
Regardless of the size of the input array, the amount of extra memory used does not increase.
Thus, Selection Sort is considered an in-place sorting algorithm, meaning it sorts the array without needing extra space proportional to the number of elements.
Stability of Algorithms
Selection Sort is not a stable sorting algorithm because it can change the relative order of equal elements.
As the algorithm repeatedly finds the smallest element in the unsorted portion and moves it to the front, it may swap equal elements, which disrupts their original order. For example, if two identical elements are swapped during the process, their initial sequence can be altered.
This swapping of elements can lead to the loss of the original order among equal items, making Selection Sort unstable.
Application of Selection Sort
Sorting Small Lists: Effective for small datasets.
Swapping Cost is Not a Concern: Ideal when swapping elements is inexpensive.
Checking All Elements: Necessary when every element must be checked.
Memory Write Cost Matters: Beneficial for systems where writing to memory is costly, as it performs fewer swaps O(n) compared to Bubble Sort O(n²).