SelectionSort in JAVA

Today, I will be show another comparative sorting algorithm known as Selection Sort. Selection sort works by finding a smaller element downstream from the current element and swapping the two per element of an array.

Setup

# Given an array:
# [9, 47, 38, 5, 40, 99, 3]
# Resultant array:
# [3, 5, 9, 38, 40, 47, 99]

Time & Space

As with insertion sort, selection sort also has the time complexity of O(n^2). The worse case scenario is when the array is sorted in the reversed order of the desired order. In this case, a swap will take place for each iteration. The space complexity of this algorithm is O(1) because this can be done in-place.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    if (n == 0 || n == 1) return;

    for (int i = 0; i < n; i++) {
        int i_min = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[i_min]) {
                i_min = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[i_min];
        arr[i_min] = temp;
    }
}

This article is my 20th oldest. It is 191 words long, and it’s got 0 comments for now.