Java Program for Selection Sort with Example and Explanation

A Java program for selection sort uses nested loops to find the smallest element and swap it with the current position; for example, for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) minIndex = j; } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } sorts the array in ascending order.

Examples

Inputarr = {5, 3, 8, 4, 2}

OutputSorted array: 2 3 4 5 8

Inputarr = {1, 2, 3, 4, 5}

OutputSorted array: 1 2 3 4 5

Inputarr = {9}

OutputSorted array: 9

How to Think About It

To sort an array using selection sort, think of finding the smallest number in the unsorted part and swapping it with the first unsorted element. Repeat this by moving the boundary of the sorted part one step forward until the whole array is sorted.

Algorithm

1

Start from the first element of the array.

2

Find the smallest element in the unsorted part of the array.

3

Swap the smallest element found with the first unsorted element.

4

Move the boundary of the sorted part one step forward.

5

Repeat steps 2-4 until the entire array is sorted.

Code

java

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        selectionSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output

Sorted array: 2 3 4 5 8 

Dry Run

Let's trace the array {5, 3, 8, 4, 2} through the selection sort code.

1

First outer loop (i=0)

Find smallest from index 0 to end: smallest is 2 at index 4; swap arr[0] and arr[4]. Array becomes {2, 3, 8, 4, 5}.

2

Second outer loop (i=1)

Find smallest from index 1 to end: smallest is 3 at index 1; swap arr[1] and arr[1]. Array stays {2, 3, 8, 4, 5}.

3

Third outer loop (i=2)

Find smallest from index 2 to end: smallest is 4 at index 3; swap arr[2] and arr[3]. Array becomes {2, 3, 4, 8, 5}.

4

Fourth outer loop (i=3)

Find smallest from index 3 to end: smallest is 5 at index 4; swap arr[3] and arr[4]. Array becomes {2, 3, 4, 5, 8}.

Iteration	Array State
i=0	2 3 8 4 5
i=1	2 3 8 4 5
i=2	2 3 4 8 5
i=3	2 3 4 5 8

Why This Works

Step 1: Find the minimum element

The inner loop uses if (arr[j] < arr[minIndex]) to find the smallest element in the unsorted part.

Step 2: Swap the minimum with the first unsorted

After finding the smallest element, swapping it with the element at the current position i places it in the sorted part.

Step 3: Repeat until sorted

The outer loop moves forward, shrinking the unsorted part until the entire array is sorted.

Alternative Approaches

Bubble Sort

java

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        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 temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Bubble sort repeatedly swaps adjacent elements and is simpler but usually slower than selection sort.

Insertion Sort

java

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        insertionSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Insertion sort builds the sorted array one element at a time and is efficient for nearly sorted data.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, resulting in O(n^2) time regardless of input order.

Space Complexity

It sorts the array in place using only a few extra variables, so space complexity is O(1).

Which Approach is Fastest?

Selection sort is simple but slower than more advanced algorithms like quicksort; alternatives like insertion sort can be faster on nearly sorted data.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Small arrays, simple implementation
Bubble Sort	O(n^2)	O(1)	Teaching sorting basics, simple swaps
Insertion Sort	O(n^2)	O(1)	Nearly sorted arrays, adaptive sorting