Selection Sort
What is Selection Sort?
Selection sort divides the array into a sorted and unsorted portion. In each pass, it selects the minimum element from the unsorted portion and places it at the beginning of the unsorted portion. It makes exactly n-1 swaps — useful when write operations are expensive.
| Case | Time | Space | Stable? |
|---|---|---|---|
| Best / Average / Worst | O(n²) | O(1) | No |
| Swaps | O(n) | — | — |
How it Works
For array [29, 10, 14, 37, 13]:
- Pass 1: Find min in [29,10,14,37,13] = 10 → swap with 29 →
[10, 29, 14, 37, 13] - Pass 2: Find min in [29,14,37,13] = 13 → swap with 29 →
[10, 13, 14, 37, 29] - Pass 3: Find min in [14,37,29] = 14 → no swap →
[10, 13, 14, 37, 29] - Pass 4: Find min in [37,29] = 29 → swap with 37 →
[10, 13, 14, 29, 37]✓
import java.util.Arrays;
public class SelectionSort {
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find minimum element in arr[i..n-1]
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap minimum with first element of unsorted portion
if (minIdx != i) {
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
}
// Selection sort — descending order
static void selectionSortDesc(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int maxIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIdx]) maxIdx = j;
}
int temp = arr[maxIdx];
arr[maxIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37, 13};
System.out.println("Before: " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("After: " + Arrays.toString(arr));
// After: [10, 13, 14, 29, 37]
int[] arr2 = {5, 3, 8, 1, 9};
selectionSortDesc(arr2);
System.out.println("Desc: " + Arrays.toString(arr2));
// Desc: [9, 8, 5, 3, 1]
}
}
/*
* Key property: always makes exactly n-1 swaps
* regardless of input order.
* Good when: write operations are expensive (e.g., flash memory)
* Bad when: large datasets — O(n²) comparisons always
*/Step-by-Step Trace
For array [29, 10, 14, 37, 13]:
| Pass | Unsorted Portion | Min Found | Array After Swap |
|---|---|---|---|
| 1 | [29, 10, 14, 37, 13] | 10 at index 1 | [10, 29, 14, 37, 13] |
| 2 | [29, 14, 37, 13] | 13 at index 4 | [10, 13, 14, 37, 29] |
| 3 | [14, 37, 29] | 14 at index 2 | [10, 13, 14, 37, 29] |
| 4 | [37, 29] | 29 at index 4 | [10, 13, 14, 29, 37] |
| Done | — | — | [10, 13, 14, 29, 37] ✓ |
Notice: exactly 4 swaps for 5 elements (n-1 swaps always). This is selection sort's key property.
When to Use Selection Sort
- When write operations are expensive — it makes exactly n-1 swaps regardless of input
- Small arrays where simplicity matters
- Avoid for large datasets — O(n²) comparisons always, even for sorted input