15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Selection sort grows a sorted prefix from the left. For each position it scans the rest of the array for the smallest value and swaps that value into place. It always makes n(n-1)/2 comparisons, so it is O(n^2) on every input, with at most n - 1 swaps and O(1) extra space.
| Time, all cases | O(n^2), always n(n-1)/2 comparisons |
|---|---|
| Swaps | At most n - 1, one per outer pass |
| Extra space | O(1), sorts in place |
| Stable | No, long-distance swaps can reverse equal keys |
| Invariant | Before pass i, positions 0..i-1 hold the i smallest values, sorted |
Selection Sort assumes you already know two sorting ideas:
Bubble Sort repeatedly moves large values rightward through adjacent swaps. Selection Sort follows these steps:
The part already fixed is the sorted prefix. The part still being searched is the unsorted suffix.
Selection Sort here uses ascending order.
Use this array throughout:
1Index: 0 1 2 3
2Value: [3, 1, 2, 1]At the start, no position is fixed.
1[3, 1, 2, 1]
2 ^
3sorted prefix: empty
4unsorted suffix: indices 0 through 3Start at index 0. The value placed there must be the minimum of the whole array.
Scan the array:
0 as the current minimum: value 3.1: value 1. Since 1 < 3, remember index 1.2: value 2. It is not smaller than 1.3: value 1. It is equal to the current minimum, not strictly smaller, so keep the earlier minimum at index 1.The minimum is 1 at index 1. Swap it with the value at the prefix boundary, index 0.
1[1, 3, 2, 1]
2 ^
3sorted prefix: [1]
4unsorted suffix: indices 1 through 3The first placement fixes index 0. Then index 1 becomes the next prefix boundary.
Selection Sort on [3, 1, 2, 1]: scan the unsorted suffix for the smallest value (a tie keeps the earlier one), then swap it into the boundary position i. Three placements fix the array.
Track the index of the smallest value seen so far.
| Scan step | Examined index | Examined value | Current minimum index | Current minimum value |
|---|---|---|---|---|
| initialize | 0 | 3 | 0 | 3 |
| scan | 1 | 1 | 1 | 1 |
| scan | 2 | 2 | 1 | 1 |
| scan | 3 | 1 | 1 | 1 |
Swap indices 0 and 1.
1[3, 1, 2, 1] -> [1, 3, 2, 1]The prefix is now fixed:
1[1 | 3, 2, 1]Do not scan index 0 again. It is already in its final position.
| Scan step | Examined index | Examined value | Current minimum index | Current minimum value |
|---|---|---|---|---|
| initialize | 1 | 3 | 1 | 3 |
| scan | 2 | 2 | 2 | 2 |
| scan | 3 | 1 | 3 | 1 |
Swap indices 1 and 3.
1[1, 3, 2, 1] -> [1, 1, 2, 3]Now two positions are fixed.
1[1, 1 | 2, 3]| Scan step | Examined index | Examined value | Current minimum index | Current minimum value |
|---|---|---|---|---|
| initialize | 2 | 2 | 2 | 2 |
| scan | 3 | 3 | 2 | 2 |
The minimum is already at index 2. No swap is needed.
1[1, 1, 2, 3]There is no need for an outer iteration at index 3. Once positions 0 through 2 are fixed, the final remaining value must occupy the final position.
The placements follow this pattern:
1After i positions have been fixed,
2positions 0 through i - 1 are sorted and contain the i smallest input elements.
3Everything from i onward is still the remaining input.The loop invariant is:
Before outer index
i, positions0throughi - 1contain theismallest input elements in nondecreasing order; positionsithroughn - 1contain the remaining elements.
For the example:
Before outer index i | Array | Sorted prefix | Remaining suffix |
|---|---|---|---|
| 0 | [3,1,2,1] | empty | [3,1,2,1] |
| 1 | [1,3,2,1] | [1] | [3,2,1] |
| 2 | [1,1,2,3] | [1,1] | [2,3] |
The boundary i separates positions that must never be searched again from positions that still need work.
At each prefix boundary i:
a[i] as the smallest value in the suffix for now.minIndex.i + 1 through the final index.a[minIndex], update minIndex.a[i] with a[minIndex].Use a strict comparison:
1a[j] < a[minIndex]For equal values, this keeps the first minimum encountered during that suffix scan. It matches the trace above: when the scan at index 0 reaches the second 1, it keeps the first 1 at index 1.
That strict comparison does not make ordinary swap-based Selection Sort stable. A later long-distance swap can still reverse equal-key records.
Input: mutable array a of comparable values, in any order.
Return value: the same array reference after sorting it in nondecreasing order.
Mutation behavior: rearranges values inside a; does not allocate another array.
Boundary behavior: arrays of length 0 or 1 are unchanged.
Helper contract: swap(a, p, q) exchanges the values at valid indices p and q in a and changes no other array position.
11 function selectionSort(a):
22 n <- length(a)
33
44 for i <- 0 to n - 2:
55 minIndex <- i
66
77 for j <- i + 1 to n - 1:
88 if a[j] < a[minIndex]:
99 minIndex <- j
1010
1111 if minIndex != i:
1212 swap(a, i, minIndex)
1313
1414 return aThe inner loop finds the minimum index in the suffix i through n - 1.
The swap is outside the inner loop. That placement happens once after the complete scan, not every time a smaller candidate appears.
Run the pseudocode on the original array.
1a = [3, 1, 2, 1]| Line | Action | Array | i | j | minIndex |
|---|---|---|---|---|---|
| 2 | n <- length(a) | [3,1,2,1] | — | — | — |
| 4 | begin outer iteration | [3,1,2,1] | 0 | — | — |
| 5 | minIndex <- i | [3,1,2,1] | 0 | — | 0 |
| 7 | examine next suffix position | [3,1,2,1] | 0 | 1 | 0 |
| 8–9 | 1 < 3, so update | [3,1,2,1] | 0 | 1 | 1 |
| 7 | examine next suffix position | [3,1,2,1] | 0 | 2 | 1 |
| 8 | 2 < 1 is false | [3,1,2,1] | 0 | 2 | 1 |
| 7 | examine next suffix position | [3,1,2,1] | 0 | 3 | 1 |
| 8 | 1 < 1 is false | [3,1,2,1] | 0 | 3 | 1 |
| 11–12 | indices differ, swap 0 and 1 | [1,3,2,1] | 0 | — | 1 |
The first outer iteration is complete. Index 0 contains the smallest value.
1[1 | 3, 2, 1]Continue.
| Line | Action | Array | i | j | minIndex |
|---|---|---|---|---|---|
| 4 | begin outer iteration | [1,3,2,1] | 1 | — | — |
| 5 | minIndex <- i | [1,3,2,1] | 1 | — | 1 |
| 7 | examine next suffix position | [1,3,2,1] | 1 | 2 | 1 |
| 8–9 | 2 < 3, so update | [1,3,2,1] | 1 | 2 | 2 |
| 7 | examine next suffix position | [1,3,2,1] | 1 | 3 | 2 |
| 8–9 | 1 < 2, so update | [1,3,2,1] | 1 | 3 | 3 |
| 11–12 | indices differ, swap 1 and 3 | [1,1,2,3] | 1 | — | 3 |
Now the first two positions are fixed.
1[1, 1 | 2, 3]Final outer iteration:
| Line | Action | Array | i | j | minIndex |
|---|---|---|---|---|---|
| 4 | begin outer iteration | [1,1,2,3] | 2 | — | — |
| 5 | minIndex <- i | [1,1,2,3] | 2 | — | 2 |
| 7 | examine next suffix position | [1,1,2,3] | 2 | 3 | 2 |
| 8 | 3 < 2 is false | [1,1,2,3] | 2 | 3 | 2 |
| 11 | minIndex = i, so do not swap | [1,1,2,3] | 2 | — | 2 |
| 14 | return a | [1,1,2,3] | — | — | — |
We show that the algorithm returns the array in nondecreasing order while keeping exactly the input elements.
At the start of an outer iteration, minIndex is set to i. So it names a minimum of the one-element scanned region containing only a[i].
Each inner-loop step examines one new suffix value, a[j].
a[j] is smaller than a[minIndex], line 9 updates minIndex to j. It now names the minimum of every suffix position scanned so far.minIndex still names a minimum of the scanned positions.When the inner loop ends, every position from i through n - 1 has been examined. Therefore, minIndex identifies a minimum of the entire unsorted suffix.
Before the first outer iteration, i = 0.
The sorted prefix contains no elements. An empty prefix is sorted and contains the zero smallest input elements. The entire array is the remaining suffix. So the invariant holds initially.
Assume the invariant holds before outer index i.
The inner scan finds a minimum value in positions i through n - 1. Swapping that minimum into a[i] does not lose an element: it only exchanges two existing array values.
The old prefix a[0..i-1] already contains the i smallest input elements in nondecreasing order. Every one of those values is no greater than every remaining suffix value. The selected suffix minimum is therefore no smaller than the last prefix value when the prefix is nonempty.
After placing that selected minimum at a[i]:
0 through i are in nondecreasing order;i + 1 smallest input elements;i + 1 through n - 1.So the invariant holds for the next outer index.
The outer loop ends after handling indices 0 through n - 2.
At that point, the invariant says positions 0 through n - 2 contain the n - 1 smallest elements in nondecreasing order. The one remaining input element is at index n - 1, and it cannot be smaller than an element in the sorted prefix. Therefore the entire array is sorted in nondecreasing order.
Because the only modification is swapping array elements, the output is a permutation of the input.
A stable sort preserves the relative order of records with equal keys. Use tags to tell equal keys apart:
1[(2,A), (2,B), (1,X)]At index 0, the minimum is (1,X) at index 2. Swapping it with (2,A) gives:
1[(1,X), (2,B), (2,A)]The equal-key records were originally ordered A then B. They are now ordered B then A.
The output is sorted by key. The algorithm is not stable.
Let n be the array length.
The outer loop runs once for each prefix position from 0 through n - 2. The suffix scans have these lengths:
1First scan: n - 1 comparisons
2Second scan: n - 2 comparisons
3...
4Last scan: 1 comparisonThe total number of value comparisons is:
1(n - 1) + (n - 2) + ... + 1
2= n(n - 1) / 2For the worked array, n = 4, so the scans perform:
13 + 2 + 1 = 6 comparisonsThe scan length depends only on the array length, not on whether the input begins sorted, reversed, or mixed. Therefore every input order takes O(n^2) comparisons.
Each outer iteration performs at most one swap:
1At most n - 1 swapsSo the number of swaps is O(n).
The algorithm stores:
nijminIndexswapThese are constant-sized extra variables. The algorithm uses O(1) auxiliary space, excluding the input array itself.
The comparison and swap accounting follows the standard selection-sort analysis described in the supplied elementary-sorts source: Elementary Sorts.
Incorrect update:
1if a[j] <= a[minIndex]:
2 minIndex <- jSmallest exposing input:
1[(2,A), (2,B)]At i = 0:
minIndex = 0, pointing to (2,A).j = 1, 2 <= 2 is true.minIndex to 1.0 and 1.Wrong result:
1[(2,B), (2,A)]The keys remain sorted, but equal records were disturbed unnecessarily.
Correction:
1if a[j] < a[minIndex]:
2 minIndex <- jUse the strict comparison for the usual Selection Sort trace. Do not claim that basic swap-based Selection Sort is stable: its long-distance swaps can reverse equal-key records in other inputs.
Incorrect idea:
1if a[j] < a[i]:
2 swap(a, i, j)Smallest exposing input:
1[3, 1, 2]The wrong process is:
1Start: [3,1,2]
2See 1: swap immediately -> [1,3,2]The swap places 1 correctly, but the method is no longer Selection Sort’s minimum-selection process. It changes the boundary value while still scanning and can make extra changes instead of making one final placement after identifying the minimum.
Correction:
1Scan the whole suffix.
2Record minIndex.
3Make one swap after the scan.Incorrect scan boundary:
1for j <- 0 to n - 1:Smallest exposing input:
1[1, 2, 3]After index 0 has been fixed, later iterations should leave it alone. Scanning from 0 again includes already-fixed positions in the candidate search. That breaks the meaning of the sorted prefix and can move a value that was already placed.
Correction:
1for j <- i + 1 to n - 1:The scan must begin immediately after the current boundary because indices before i are fixed.
Check these inputs against the pseudocode:
| Input | Result | Why |
|---|---|---|
[] | [] | The outer loop has no iterations. |
[9] | [9] | The outer loop has no iterations. |
[1,2,3] | [1,2,3] | It remains sorted, but the algorithm still scans suffixes of lengths 2 and 1. |
[2,2,1] | [1,2,2] | The minimum 1 is selected and placed first. |
[(2,A),(2,B),(1,X)] | [(1,X),(2,B),(2,A)] | Sorted by key, but not stable. |
Implement ascending Selection Sort with this contract:
i, locate a minimum index.The tests verify sorted permutations, including arrays with duplicates and negative values.
1
2def selection_sort(a):
3 comparisons = swaps = 0
4 n = len(a)
5 for i in range(n - 1):
6 min_index = i
7 for j in range(i + 1, n):
8 comparisons += 1
9 if a[j] < a[min_index]: # strict: keep the first minimum
10 min_index = j
11 if min_index != i:
12 a[i], a[min_index] = a[min_index], a[i] # one swap per outer pass
13 swaps += 1
14 return comparisons, swaps
15
16nums = [3, 1, 2, 1]
17comparisons, swaps = selection_sort(nums)
18print(nums)
19print("comparisons:", comparisons)
20print("swaps:", swaps)1
2import java.util.Arrays;
3
4public class Main {
5 static int comparisons = 0, swaps = 0;
6
7 static void selectionSort(int[] a) {
8 int n = a.length;
9 for (int i = 0; i < n - 1; i++) {
10 int minIndex = i;
11 for (int j = i + 1; j < n; j++) {
12 comparisons++;
13 if (a[j] < a[minIndex]) minIndex = j; // strict: keep the first minimum
14 }
15 if (minIndex != i) {
16 int tmp = a[i]; // one swap per outer pass
17 a[i] = a[minIndex];
18 a[minIndex] = tmp;
19 swaps++;
20 }
21 }
22 }
23
24 public static void main(String[] args) {
25 int[] nums = {3, 1, 2, 1};
26 selectionSort(nums);
27 System.out.println(Arrays.toString(nums));
28 System.out.println("comparisons: " + comparisons);
29 System.out.println("swaps: " + swaps);
30 }
31}1
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7int comparisons = 0, swaps = 0;
8
9void selectionSort(vector<int>& a) {
10 int n = a.size();
11 for (int i = 0; i < n - 1; i++) {
12 int minIndex = i;
13 for (int j = i + 1; j < n; j++) {
14 comparisons++;
15 if (a[j] < a[minIndex]) minIndex = j; // strict: keep the first minimum
16 }
17 if (minIndex != i) {
18 swap(a[i], a[minIndex]); // one swap per outer pass
19 swaps++;
20 }
21 }
22}
23
24int main() {
25 vector<int> nums = {3, 1, 2, 1};
26 selectionSort(nums);
27 cout << "[";
28 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
29 cout << "]" << endl;
30 cout << "comparisons: " << comparisons << endl;
31 cout << "swaps: " << swaps << endl;
32}1
2function selectionSort(a) {
3 let comparisons = 0;
4 let swaps = 0;
5 const n = a.length;
6 for (let i = 0; i < n - 1; i++) {
7 let minIndex = i;
8 for (let j = i + 1; j < n; j++) {
9 comparisons++;
10 if (a[j] < a[minIndex]) minIndex = j; // strict: keep the first minimum
11 }
12 if (minIndex !== i) {
13 [a[i], a[minIndex]] = [a[minIndex], a[i]]; // one swap per outer pass
14 swaps++;
15 }
16 }
17 return { comparisons, swaps };
18}
19
20const nums = [3, 1, 2, 1];
21const { comparisons, swaps } = selectionSort(nums);
22console.log(`[${nums.join(', ')}]`);
23console.log(`comparisons: ${comparisons}`);
24console.log(`swaps: ${swaps}`);Take [3, 1, 2, 1]. The first scan finds 1 at index 1 and swaps it with 3: [1, 3, 2, 1]. The second finds the last 1 at index 3 and swaps it with 3: [1, 1, 2, 3]. The third scan finds 2 already in place.
The scan length depends only on n, not on the order of the values. The scans cost (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 comparisons whether the input is sorted, reversed or mixed.
No. On [(2,A), (2,B), (1,X)] the minimum (1,X) swaps with (2,A), giving (1,X), (2,B), (2,A). The keys are sorted but A and B changed order.
At most n - 1, one per outer pass, and none when the minimum is already in place. That is why it suits cases where writes cost more than comparisons.
Both are O(n^2), but selection sort makes at most n - 1 swaps while bubble sort can make one per inversion. Bubble sort can stop early and is stable. Selection sort cannot stop early.