Selection Sort in Java

Imagine picking a cricket team from a group of friends by height, shortest first. You look at everyone, pick the shortest, and send them to stand first in line. Then you look at everyone who is left, pick the shortest of them, and send them second. You keep going until nobody is left. That is selection sort: each round selects the smallest remaining item and puts it in the next place. In this lesson, you will learn how selection sort works, trace it round by round, see how it compares with bubble sort, and understand why it isn't stable.

What Is Selection Sort?

Selection sort in Java is a sorting algorithm that is used to arrange elements by repeatedly finding the minimum element in the unsorted part and swapping it with the first unsorted element. The array is divided into a sorted part on the left, which grows by one element each round, and an unsorted part on the right.

• It sorts in place with O(1) extra memory.
• It makes at most n - 1 swaps, fewer than bubble sort.
• It always makes about n² / 2 comparisons, even on sorted input.
• It is not stable.

How It Works

1. Find the smallest element in positions 0 to n - 1. Swap it into position 0.
2. Find the smallest in positions 1 to n - 1. Swap it into position 1.
3. Repeat for positions 2, 3, ..., until one element is left. It is already in place.

Selection Sort with a Trace

Let's see an example that sorts the same five marks used in "Bubble Sort in Java" and prints each round.

import java.util.Arrays;
 
public class SelectionSort {
    static void selectionSort(int[] a) {
        for (int start = 0; start < a.length - 1; start++) {
            int minIndex = start;
            for (int i = start + 1; i < a.length; i++) {
                if (a[i] < a[minIndex]) {
                    minIndex = i;
                }
            }
            int temp = a[start];
            a[start] = a[minIndex];
            a[minIndex] = temp;
            System.out.println("round " + (start + 1) + ": smallest is "
                    + a[start] + " -> " + Arrays.toString(a));
        }
    }
 
    public static void main(String[] args) {
        int[] marks = {29, 10, 14, 37, 13};
        selectionSort(marks);
        System.out.println("sorted: " + Arrays.toString(marks));
    }
}

round 1: smallest is 10 -> [10, 29, 14, 37, 13]
round 2: smallest is 13 -> [10, 13, 14, 37, 29]
round 3: smallest is 14 -> [10, 13, 14, 37, 29]
round 4: smallest is 29 -> [10, 13, 14, 29, 37]
sorted: [10, 13, 14, 29, 37]

Explanation:

1. Round 1 scans all five values, finds 10 at index 1, and swaps it with 29 at index 0.
2. Round 2 scans indexes 1 to 4, finds 13, and swaps it into index 1. The left part [10, 13] is now final.
3. Each round remembers the index of the smallest value (minIndex) and does one swap at the end, instead of swapping as it goes.
4. After n - 1 = 4 rounds, the last element is automatically the largest.

Why Selection Sort Isn't Stable

A sort is stable if equal elements keep their original order. Selection sort's long-distance swap can jump an element over an equal one.

import java.util.Arrays;
 
public class Unstable {
    record Student(String name, int marks) {}
 
    public static void main(String[] args) {
        Student[] s = {
            new Student("Navika", 80),
            new Student("Srihitha", 80),
            new Student("Advitha", 70)
        };
        for (int start = 0; start < s.length - 1; start++) {
            int min = start;
            for (int i = start + 1; i < s.length; i++) {
                if (s[i].marks() < s[min].marks()) {
                    min = i;
                }
            }
            Student t = s[start];
            s[start] = s[min];
            s[min] = t;
        }
        System.out.println(Arrays.toString(s));
    }
}

[Student[name=Advitha, marks=70], Student[name=Srihitha, marks=80], Student[name=Navika, marks=80]]

Explanation: Navika and Srihitha both have 80, and Navika came first. In round 1, Advitha (70) is swapped with Navika, which sends Navika behind Srihitha. The two 80s have changed order, so the sort isn't stable. When you sort objects by one field after sorting by another, stability matters; Java's List.sort and Arrays.sort for objects are stable.

Complexity

Selection Sort vs Bubble Sort

Common Mistakes

Swapping inside the inner loop. That turns it into a slower, messier bubble sort. Track minIndex and swap once per round.

Starting the inner loop at start instead of start + 1. It still works but compares an element with itself.

Expecting it to be fast on sorted data. Unlike insertion sort and bubble sort with an early exit, it scans everything every time.

Practice

1. Easy: Change the program to select the largest element each round and swap it to the end. The result should still be ascending.
2. Harder: Count the comparisons and swaps when sorting {10, 13, 14, 29, 37} (already sorted). Compare with bubble sort's early-exit version on the same input.

Key Takeaways