Selection Sort

Selection Sort is a simple in-place sorting algorithm that repeatedly finds the smallest element in the unsorted part of an array and moves it to its correct position at the front. It runs in O(n²) time in all cases, uses O(1) extra memory, and performs at most n−1 swaps. Because it is intuitive and easy to code in any language, Selection Sort is one of the first sorting methods taught to beginners in Java.

Idea Behind Selection Sort

The essence of Selection Sort can be described in three steps:

1. Find the minimum element in the unsorted part of the array.
2. Swap it with the first element of that unsorted part.
3. Repeat the process for the remaining, still unsorted portion of the array.

With each pass of the outer loop, the boundary of the sorted part shifts one position to the right, and the smallest remaining values line up at the beginning of the array one after another.

Visualization example:

Selection Sort Implementation in Java

Let’s look at the implementation. The outer for loop controls the number of passes, while the inner loop searches for the smallest value in the current pass. Note that the inner search does not start from the very beginning of the array: elements found on previous steps are already in place and are skipped.

public class SelectionSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {    // i - current step
            int pos = i;
            int min = array[i];
            // search for the minimum element
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    pos = j;    // pos - index of the smallest element
                    min = array[j];
                }
            }
            array[pos] = array[i];
            array[i] = min;    // swap smallest with array[i]
        }
    }
}

Example Usage

Below is an example with several test arrays. It clearly demonstrates how Selection Sort behaves on different inputs — from an empty array to a fully reversed one.

import java.util.Arrays;

public class SelectionSorterExample {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            SelectionSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

Time Complexity and Stability

Selection Sort always performs the same number of comparisons regardless of the input: the outer loop runs n times and the inner loop runs on average n/2 times. As a result, its time complexity is identical in the best, average and worst cases — there is no early exit even on an already sorted array.

Advantages and Disadvantages of Selection Sort

This algorithm is not the fastest choice, especially for large data volumes. Still, it is worth knowing because it illustrates the principles of in-place sorting and the repeated-minimum-selection technique. Compared with bubble sort, Selection Sort makes the same number of comparisons but noticeably fewer swaps.

Common Mistakes

• Starting the inner loop from zero. The search for the minimum must begin at index i + 1, not at the start of the array — otherwise the pass loses its meaning and you make extra, pointless comparisons.
• Forgetting to store the minimum index. The swap must use the saved position pos, not the first smaller element you happen to see; otherwise the array will not be sorted correctly.
• Expecting a speed-up on nearly sorted data. Unlike insertion sort, Selection Sort always performs O(n²) comparisons — there is no early termination.
• Confusing it with bubble sort. Both are O(n²), but bubble sort swaps adjacent elements on every comparison, while Selection Sort performs just one swap per pass.

Conclusion

Selection Sort in Java is a fundamental yet important algorithm that every beginner should understand. Despite its simplicity and relatively low O(n²) efficiency, it gives a solid feel for how arrays, nested loops and value swapping work. In real projects you would use the built-in Arrays.sort() for large data, but understanding simple sorts helps in interviews and when studying more advanced algorithms.