Understanding Selection Sort Algorithm (with Examples in Java)

In Selection Sort, we iterate through an unsorted list, and on each iteration, the smallest (or largest, if we are sorting in descending order) element is selected and placed at the beginning of the list. This process goes on until all the elements in the list are sorted.

Working of Selection Sort

Let's say we want to sort this array in ascending order

First Iteration

The goal of the iteration is to place the smallest element in the unsorted array at the beginning. We start by setting the first element in the unsorted list as the minimum.

We then compare the minimum with the second element, and set the second element as the minimum if it is smaller.

This is repeated for the remaining elements and eventually, the smallest element is set as minimum.

We then swap the minimum element with the element at the beginning of the unsorted list.

Elements that have moved to their correct position are said to be sorted. In subsequent iterations, we will only compare the unsorted elements.

Subsequent Iterations

This process is repeated for all iterations until the array is sorted.

We iterate through the array n-1 times, where n is the length of the array. That is, since our array has six elements, we iterate through the array only five times. This is because, after the fifth iteration, five elements have been placed in their correct position, therefore the final unsorted element is considered sorted. After all iterations, we will have a sorted array.

Implementation of Selection Sort

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr){
        int size = arr.length;

        // loop through array size-1 times
        for (int i = 0; i < size-1; i++) {
            int minIndex = i; // set the current index as the minimum

            // loop through the unsorted elements
            for (int j = i+1; j < size; j++) {
                if(arr[j] < arr[minIndex]) minIndex = j;
            }

            // place the minimum element at the current index
            if (minIndex != i){
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

Running this code will print the following output to the console:

Unsorted array: [8, 2, 6, 4, 9, 1]
Sorted array: [1, 2, 4, 6, 8, 9]

Complexity of Selection Sort

Time Complexity:

Best Case (O(n²)):

Selection Sort always scans the entire unsorted portion of the array to find the minimum element in each pass, whether the array is already sorted or not.

Average Case (O(n²)):

Like the best case, the number of comparisons does not depend on the initial ordering.

Worst Case (O(n²)):

Similar to the average and best case, the number of comparisons does not depend on the initial ordering.

Space Complexity O(1):

Selection Sort is an in-place sorting algorithm, that is, it does not require any extra memory proportional to the size of the input array.

Conclusion

Selection Sort has a time complexity of O(n²) in all cases. It is not suitable to use when working with large datasets due to its high time complexity. Use Selection Sort when working with small datasets, or when you are not concerned with complexity.