Selection sort is an in-place comparison sort that repeatedly finds the smallest element of the unsorted part of an array and swaps it to the front of that part. The sorted part grows by one element per step, and after n – 1 steps the whole array is sorted.
Selection sort is mainly taught in courses, and it is useful in the rare cases where writing to memory is expensive, because it makes at most n – 1 swaps. Its O(n2) comparisons make it too slow for large arrays.
The following example sorts the page counts of five books with the selectionSort() method from section 2.
int[] pages = {7, 4, 9, 1, 5};
selectionSort(pages);
int[] sorted = pages; // [1, 4, 5, 7, 9]Only two swaps are needed for these five values. The steps come first in a diagram, followed by the code, an explanation of why selection sort is not stable and how to fix that, and the one situation where it beats the other simple sorts.
1. Selection Sort Algorithm
Selection sort splits the array into a sorted part on the left and an unsorted part on the right. At the start, the sorted part is empty. Each step does two things.
- It scans the unsorted part and remembers the index of the smallest value.
- It swaps that value with the first element of the unsorted part, which moves the boundary one position to the right.
The smallest value of the unsorted part is always larger than or equal to everything in the sorted part, so a value never moves again once it is placed.
In step 1, the scan finds 1 at index 3 and swaps it with 7. In steps 2 and 4, the smallest value is already in place, so a careful implementation skips the swap. The array of 5 elements needs 4 steps and only 2 swaps.
2. Selection Sort Program in Java
The outer loop moves the boundary i, and the inner loop finds the index of the smallest value from i + 1 to the end. Both versions are in the Core-Java repository as a runnable Java 25 class.
static void selectionSort(int[] a) {
if (a == null) {
return;
}
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (min != i) { // skip useless swaps
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}int[] one = {42};
selectionSort(one);
int[] single = one; // [42]
int[] repeated = {3, 1, 3, 1};
selectionSort(repeated);
int[] sortedRepeated = repeated; // [1, 1, 3, 3]2.1. Selection Sort with a Comparator
To sort strings, objects or in descending order, we compare through a Comparator instead of with <.
static <T> void selectionSort(T[] a, Comparator<? super T> cmp) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (cmp.compare(a[j], a[min]) < 0) {
min = j;
}
}
if (min != i) {
T tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}String[] cities = {"Pune", "Agra", "Delhi"};
selectionSort(cities, Comparator.naturalOrder());
String[] alphabetical = cities; // [Agra, Delhi, Pune]
Integer[] heights = {7, 4, 9, 1, 5};
selectionSort(heights, Comparator.reverseOrder());
Integer[] tallestFirst = heights; // [9, 7, 5, 4, 1]3. Is Selection Sort Stable?
No, selection sort with swaps is not stable. The swap moves the first element of the unsorted part to wherever the minimum was found, and that jump can carry it past an equal element. Let us check it with real objects.
The following example sorts tasks by priority. The tasks named “write” and “test” both have priority 2 and start in that order.
record Task(String name, int priority) {}Task[] tasks = {new Task("write", 2), new Task("test", 2), new Task("deploy", 1)};
selectionSort(tasks, Comparator.comparingInt(Task::priority));
String order = Arrays.stream(tasks).map(Task::name).collect(Collectors.joining(", ")); // "deploy, test, write"In the first step, the minimum is the “deploy” task at index 2, so the “write” task moves from index 0 to index 2 and lands behind “test”. The two equal tasks have changed their order.
3.1. A Stable Selection Sort
We get a stable version by shifting instead of swapping. After finding the minimum, we remove it, shift the elements between i and the minimum one position right, and insert the minimum at i. Equal elements keep their order, but the shifting version writes up to O(n2) times, so it loses the only advantage of selection sort.
static <T> void stableSelectionSort(T[] a, Comparator<? super T> cmp) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (cmp.compare(a[j], a[min]) < 0) {
min = j;
}
}
T value = a[min];
System.arraycopy(a, i, a, i + 1, min - i); // shift right
a[i] = value;
}
}Task[] queue = {new Task("write", 2), new Task("test", 2), new Task("deploy", 1)};
stableSelectionSort(queue, Comparator.comparingInt(Task::priority));
String stableOrder = Arrays.stream(queue).map(Task::name).collect(Collectors.joining(", ")); // "deploy, write, test"When stability matters, the better choice is insertion sort or the stable Arrays.sort() for objects, which both run faster as well.
4. Selection Sort Time and Space Complexity
The inner loop always scans the whole unsorted part, whether the data is sorted or not. That gives (n – 1) + (n – 2) + … + 1 = n(n – 1)/2 comparisons in every case, so selection sort is O(n2) even for sorted input.
| Measure | Best case | Average case | Worst case |
|---|---|---|---|
| Comparisons | n(n – 1)/2 | n(n – 1)/2 | n(n – 1)/2 |
| Swaps | 0 | at most n – 1 | at most n – 1 |
| Time | O(n2) | O(n2) | O(n2) |
| Extra space | O(1) | O(1) | O(1) |
Selection sort is not adaptive, which means sorted input does not make it faster. We confirmed that on 10,000 sorted integers, where it still did 49,995,000 comparisons.
5. When Selection Sort Is the Right Choice
Selection sort keeps the number of writes low. On 10,000 integers in reverse order, we counted the swaps and shifts of each simple sort.
| Algorithm | Comparisons | Swaps or shifts |
|---|---|---|
| Selection sort | 49,995,000 | 5,000 swaps |
| Bubble sort | 49,995,000 | 49,995,000 swaps |
| Insertion sort | 49,995,000 | 49,995,000 shifts |
Firmware that keeps a small sorted table in EEPROM or flash memory, where every write wears out the chip and takes milliseconds. is where selection sort fits, because it needs at most 2(n – 1) writes in total, which matters more there than the comparison count.
For ordinary in-memory data, the comparisons dominate. On random arrays of 10,000 integers, after a JIT warm-up on Java 25, selection sort took about 50 ms, bubble sort about 110 ms and insertion sort about 5 ms, while Arrays.sort() needed about 1 ms.
6. Selection Sort FAQs
Swap counts and comparisons with insertion sort lead the follow-up questions.
6.1. How many swaps does selection sort make?
At most n – 1, one per step, and fewer when the minimum is already in place and we skip the swap. In our trace in section 1, 5 elements needed only 2 swaps.
6.2. Why is selection sort O(n^2) even when the array is sorted?
Because it cannot know that the rest of the array is sorted. Finding the minimum of the unsorted part always needs a full scan, so the comparison count does not depend on the input order.
6.3. What is the difference between selection sort and insertion sort?
Selection sort picks the smallest remaining element and puts it at the end of the sorted part. Insertion sort takes the next element and inserts it into the right place in the sorted part. Insertion sort is stable and fast on nearly sorted data, whereas selection sort makes fewer writes.
6.4. Can selection sort find the largest element first?
Yes. We search for the maximum and swap it to the end of the unsorted part, which gives the same result. Searching for both the minimum and the maximum in one scan, called double selection sort, halves the number of passes but not the comparisons.
7. Conclusion
Selection sort finds the smallest unsorted element and swaps it into place, one position per step. It always makes n(n – 1)/2 comparisons, so it is O(n2) for every input, but it needs at most n – 1 swaps and no extra memory.
The swap version is not stable, as the task example showed, and the stable shifting version gives up the low write count. In practice, selection sort only makes sense when writes are expensive.
8. References
- Algorithms, 4th Edition, Elementary Sorts
- Algorithms, 4th Edition, Sorting Applications and Stability
- Arrays (Java SE 25 API)
Happy Learning !!
can you give examples when swapping is expensive?
If we’re sorting an array of pretty large objects, swapping takes a lot of time.