5. Selection Sort

Selection sort works similarly to insertion sort with two portions, sorted and unsorted. However, instead of just simply adding elements from unsorted to sorted and correctly placing them, selection sort selects the smallest element from the unsorted portion and moves it to the end of the sorted portion.

public <T extends Comparable<? super T>> void selectionSort(T[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j].compareTo(array[minIndex]) < 0) {
                minIndex = i;
            }
        }

        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

The algorithm iterates through the list, $O(n)$, and finds the minimum value from the unsorted position, $O(n)$. So, the time complexity of selection sort is $O(n^2)$. With space complexity of $O(1)$.

Next Page →