Selection Sort
EasySelection Sort is a simple sorting algorithm that divides the input list into two parts: sorted and unsorted. It repeatedly finds the minimum element from the unsorted part and places it at the beginning.
Time Complexity
O(n²)Space Complexity
O(1)Category
Sorting
Introduction to Selection Sort
Selection Sort is a straightforward sorting algorithm that divides the input array into two regions: sorted and unsorted. It works by repeatedly finding the minimum element from the unsorted region and moving it to the sorted region.
How It Works
The algorithm operates by maintaining a boundary between sorted and unsorted portions:
1. Start with the entire array as unsorted
2. Find the minimum element in the unsorted portion
3. Swap it with the first element of the unsorted portion
4. Move the boundary one position to the right
5. Repeat until the entire array is sorted
Algorithm Complexity
Best and Worst Cases
Advantages
1. Simple and easy to understand
2. In-place sorting (minimal extra memory)
3. Performs well on small datasets
4. Guaranteed number of comparisons: n(n-1)/2
5. Useful when memory write is expensive
Disadvantages
1. Unstable sorting (doesn't preserve relative order of equal elements)
2. O(n²) time complexity is inefficient for large datasets
3. No optimization possible (always performs the same comparisons)
4. Not adaptive to existing order in the data
When to Use
Comparison with Bubble Sort
Real-world Applications
Key Takeaways
- Divides list into sorted and unsorted
- Finds minimum element repeatedly
- Non-adaptive sorting
- In-place sorting
- Unstable sorting algorithm
- Good for small datasets
Implementation
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}