Selection Sort: Algorithm, Dry Run, Code & Complexity Explained
What is Selection Sort?
Selection Sort divides the array into a sorted left portion and an unsorted right portion. In each pass it finds the minimum element in the unsorted portion and swaps it to its correct position at the boundary.
Algorithm Steps
- Assume element at position i is the minimum
- Scan from i+1 to end, updating min index if a smaller element is found
- Swap arr[i] with arr[min_idx]
- Move the sorted boundary one step right
- Repeat for n-1 passes
Code Implementation
š Python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i # assume current is min
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j # new minimum found
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arrā Java
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
}āļø C++
#include <vector>
using namespace std;
void selectionSort(vector& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}
}
š” JavaScript
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;
}
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; // swap
}
}
return arr;
}
console.log(selectionSort([20, 10, 35, 2, 15, 30]));
// Output: [2, 10, 15, 20, 30, 35]Dry Run ā arr = [20, 10, 35, 2, 15, 30]
Current minimum
Scanning range
Sorted (final)
Pass 0 (i=0) ā Scan indices 1ā5
20
idx 0
10
idx 1
35
idx 2
2
idx 3 min
15
idx 4
30
idx 5
Min = 2 at index 3. Swap arr[0] ā arr[3]
2
idx 0 ā
10
idx 1
35
idx 2
20
idx 3
15
idx 4
30
idx 5
Pass 1 (i=1) ā Scan indices 2ā5
2
idx 0 ā
10
idx 1 min
35
idx 2
20
idx 3
15
idx 4
30
idx 5
Min = 10 at index 1 ā already in place, no swap needed
2
idx 0 ā
10
idx 1 ā
35
idx 2
20
idx 3
15
idx 4
30
idx 5
Pass 2 (i=2) ā Scan indices 3ā5
Scanning: 35 ā 20 ā 15 ā (min at index 4) ā 30. Swap arr[2] ā arr[4]
2
idx 0 ā
10
idx 1 ā
15
idx 2 ā
20
idx 3
35
idx 4
30
idx 5
Pass 3 (i=3) ā Scan indices 4ā5
Min = 20 at index 3 ā already in place, no swap needed
2
idx 0 ā
10
idx 1 ā
15
idx 2 ā
20
idx 3 ā
35
idx 4
30
idx 5
Pass 4 (i=4) ā Scan index 5
Min = 30 at index 5. Swap arr[4] ā arr[5]
2
idx 0 ā
10
idx 1 ā
15
idx 2 ā
20
idx 3 ā
30
idx 4 ā
35
idx 5 ā
š Sorted: [2, 10, 15, 20, 30, 35]
Comparisons Per Pass
| Pass (i) | Comparisons | Swaps |
|---|---|---|
| 0 | 5 | 1 (20ā2) |
| 1 | 4 | 0 (already in place) |
| 2 | 3 | 1 (35ā15) |
| 3 | 2 | 0 (already in place) |
| 4 | 1 | 1 (35ā30) |
| Total | 15 = n(n-1)/2 | 3 (max n-1 swaps!) |
Time & Space Complexity
| Case | Time | Reason |
|---|---|---|
| Best | O(nĀ²) | Always scans full unsorted portion ā no early exit |
| Average | O(nĀ²) | Same scan regardless of order |
| Worst | O(nĀ²) | Same scan regardless of order |
| Space | O(1) | In-place ā only min_idx variable used |
Is Selection Sort Stable?
ā No. Swapping a non-adjacent minimum to the front can change the relative order of equal elements. Use Insertion Sort or Merge Sort when stability is required.
Selection Sort vs Bubble Sort
| Feature | Selection Sort | Bubble Sort |
|---|---|---|
| Total Swaps | O(n) ā at most n-1 | O(nĀ²) ā many per pass |
| Comparisons | O(nĀ²) | O(nĀ²) |
| Stable? | ā No | ā Yes |
| Best case | O(nĀ²) ā no improvement | O(n) ā with optimization |
| Best for | When swap cost is high (flash/disk) | Nearly sorted data |