Definition
- Selection sort – divides the array into a sorted prefix and an unsorted suffix, growing the prefix one element at a time.
- Find minimum – each pass scans the unsorted suffix to find the index of the minimum element.
- Single swap – one swap per pass places the minimum at the front of the unsorted region.
- Minimal writes – at most n - 1 swaps total, the fewest of all simple sorts.
- Not stable – the basic version is unstable because long-distance swaps can reorder equal elements.
Imagine the National Bank of India lining up account balances from smallest to largest. The clerk scans the entire pile to find the single smallest balance and places it firmly at the front. Then she scans the remaining pile to find the next smallest and places it second. She repeats, each time selecting the minimum of what is left and locking it into the next position.
Understanding the Concepts
What is selection sort?
Selection sort divides the array into two parts: a sorted prefix on the left and an unsorted suffix on the right. On each pass, it scans the unsorted suffix to find the minimum element and swaps it into the first unsorted position, growing the sorted prefix by one.
package com.bank.sort;
import java.math.BigDecimal;
import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(BigDecimal[] 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].compareTo(arr[minIdx]) < 0) {
minIdx = j;
}
}
if (minIdx != i) {
BigDecimal temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
public static void main(String[] args) {
BigDecimal[] balances = {
new BigDecimal("75000"),
new BigDecimal("25000"),
new BigDecimal("50000"),
new BigDecimal("10000")
};
selectionSort(balances);
System.out.println("Sorted: " + Arrays.toString(balances));
}
}
Sorted: [10000, 25000, 50000, 75000]
How does each pass work?
The outer loop marks the boundary between sorted and unsorted. The inner loop scans the unsorted suffix, tracking the index of the smallest element. After the inner loop, one swap places that element at the boundary.
package com.bank.sort;
public class SelectionSortTrace {
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
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;
}
int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp;
System.out.println("Pass " + (i+1) + ": min=" + arr[i]
+ " -> " + java.util.Arrays.toString(arr));
}
}
}
Pass 1: min=11 -> [11, 25, 12, 22, 64]
Pass 2: min=12 -> [11, 12, 25, 22, 64]
Pass 3: min=22 -> [11, 12, 22, 25, 64]
Pass 4: min=25 -> [11, 12, 22, 25, 64]
Why is the swap count special?
Selection sort performs exactly one swap per pass, so at most n - 1 swaps total. This is the fewest swaps of any simple sort. When writes are expensive, such as on flash memory or when each element is a large object costly to copy, selection sort minimises the number of moves.
package com.bank.sort;
public class SwapCount {
public static void main(String[] args) {
int[] arr = {50, 40, 30, 20, 10};
int swaps = 0;
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) {
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
swaps++;
}
}
System.out.println("Total swaps: " + swaps + " (max n-1 = " + (arr.length-1) + ")");
}
}
Total swaps: 2 (max n-1 = 4)
Why is selection sort not stable?
The basic version is unstable because the long-distance swap can jump an equal element past another. For example, if two equal values appear and the one later in the array gets swapped to the front, the original order of those equal elements is disrupted.
package com.bank.sort;
public class SelectionUnstable {
public static void main(String[] args) {
// Two elements with value 5: "5a" at index 0, "5b" at index 2
int[] vals = {5, 3, 5, 1};
String[] tags = {"5a", "3", "5b", "1"};
// Selection sort
for (int i = 0; i < vals.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < vals.length; j++) {
if (vals[j] < vals[minIdx]) minIdx = j;
}
int tv = vals[i]; vals[i] = vals[minIdx]; vals[minIdx] = tv;
String ts = tags[i]; tags[i] = tags[minIdx]; tags[minIdx] = ts;
}
System.out.println("Result: " + java.util.Arrays.toString(tags));
System.out.println("5b before 5a: order changed (unstable)");
}
}
Result: [1, 3, 5b, 5a]
5b before 5a: order changed (unstable)
How is selection sort different from bubble sort?
| Feature | Selection Sort | Bubble Sort |
|---|---|---|
| Mechanism | Find minimum, one swap | Swap adjacent pairs |
| Swaps per pass | 1 | Many |
| Stable | No (basic) | Yes |
| Early exit | No | Yes (swapped flag) |
| Best on | Write-expensive scenarios | Nearly-sorted data |
package com.bank.sort;
public class SelectionVsBubble {
public static void main(String[] args) {
int[] a = {5, 3, 4, 1, 2};
int selSwaps = selectionSortCount(a.clone());
int bubSwaps = bubbleSortCount(a.clone());
System.out.println("Selection swaps: " + selSwaps);
System.out.println("Bubble swaps: " + bubSwaps);
}
static int selectionSortCount(int[] arr) {
int swaps = 0;
for (int i = 0; i < arr.length-1; i++) {
int m = i;
for (int j = i+1; j < arr.length; j++) if (arr[j] < arr[m]) m = j;
if (m != i) { int t=arr[i]; arr[i]=arr[m]; arr[m]=t; swaps++; }
}
return swaps;
}
static int bubbleSortCount(int[] arr) {
int swaps = 0;
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) { int t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; swaps++; }
}
}
return swaps;
}
}
Selection swaps: 3
Bubble swaps: 7
What is the time and space complexity?
| Case | Time | Reason |
|---|---|---|
| Best | O(n^2) | Always scans full unsorted suffix |
| Average | O(n^2) | Same |
| Worst | O(n^2) | Same |
| Space | O(1) | In-place |
| Swaps | O(n) | At most n - 1 |
When should you use selection sort?
Only in two narrow cases: tiny arrays (a few elements) where the overhead does not matter, and situations where the number of writes must be absolutely minimised. In all other cases, use the library sort.
package com.bank.sort;
public class WhenToUse {
public static void main(String[] args) {
// Tiny array: selection sort is fine
int[] tiny = {3, 1, 2};
for (int i = 0; i < tiny.length-1; i++) {
int m = i;
for (int j = i+1; j < tiny.length; j++) if (tiny[j] < tiny[m]) m = j;
int t = tiny[i]; tiny[i] = tiny[m]; tiny[m] = t;
}
System.out.println(java.util.Arrays.toString(tiny));
}
}
[1, 2, 3]
What are common mistakes?
The most common mistake is assuming selection sort is stable. The long-distance swap breaks stability. Another mistake is not skipping the swap when minIdx == i, which is a wasted write.
Visual Overview
Selection Sort Pass-by-Pass:
[75000, 25000, 50000, 10000]
^sorted|----unsorted------^
Pass 1: scan unsorted, find min = 10000 at index 3
swap arr[0] <-> arr[3]
[10000, 25000, 50000, 75000]
^--sorted--|---unsorted---^
Pass 2: scan unsorted, find min = 25000 at index 1
already in place, no swap
[10000, 25000, 50000, 75000]
^----sorted----|--unsorted^
Pass 3: scan unsorted, find min = 50000 at index 2
already in place
[10000, 25000, 50000, 75000]
^------sorted------|------^
Done! Sorted prefix covers entire array.
Key Takeaway
Selection sort divides the array into a sorted prefix and an unsorted suffix. On each pass it scans the unsorted suffix to find the minimum element and swaps it into the first unsorted position, growing the sorted prefix by one. It has O(n^2) time in every case, uses O(1) extra memory, and the basic version is not stable.
Its distinguishing feature is the swap count. Selection sort performs exactly one swap per pass, at most n - 1 swaps total, which is the fewest of all simple sorts. When writes are expensive, such as on flash memory or with large objects costly to copy, selection sort minimises the number of moves.
In a banking context at the National Bank of India, selection sort is useful only conceptually for ordering a small set of flagged accounts from smallest to largest balance. In any production system, the library sort is always the right choice.
The honest senior-level assessment is that selection sort's quadratic comparisons make it unsuitable for large data, and its instability is a limitation. Its genuine niches are tiny arrays and write-minimising scenarios.
Remember one sentence: selection sort finds the minimum of the unsorted remainder and places it next, performing the fewest swaps of any simple sort but always doing quadratic comparisons.
---