Selection Sort

Selection sorting is a simple sorting algorithm. It works by looping through the array and nested in that loop is another loop which is ahead by 1 so when the first loop is on 1, the second loop will be on 2. Within the first loop we initialise a variable called min and set it equal to i.

public int[] selectionSort(int[] arrayToSort) {
    for (int i = 0; i < arrayToSort.length; i++) {
        int min = i;
        for (int j = i + 1; j < arrayToSort.length; j++) {

        }
    }
    return arrayToSort;
}

Then it compares the two numbers within the second loop and if the second number is smaller then the current minimum we store that as the new minimum.

public int[] selectionSort(int[] arrayToSort) {
    if (arrayToSort.length < 1) return arrayToSort;
    for (int i = 0; i < arrayToSort.length; i++) {
        int min = i;
        for (int j = i + 1; j < arrayToSort.length; j++) {
            if (arrayToSort[j] < arrayToSort[min]) {
                min = j;
            }
        }
    }
    return arrayToSort;
}

So now we have the information we need to actually re-arrange the array. So we will store the value of the current index, then set the value to the new minimum and then set where the minimum was to the value of the index we stored. So we basically just swapped them around.

public int[] selectionSort(int[] arrayToSort) {
    if (arrayToSort.length < 1) return arrayToSort;
    for (int i = 0; i < arrayToSort.length; i++) {
        int min = i;
        for (int j = i + 1; j < arrayToSort.length; j++) {
            if (arrayToSort[j] < arrayToSort[min]) {
                min = j;
            }
        }
        int temp = arrayToSort[i];
        arrayToSort[i] = arrayToSort[min];
        arrayToSort[min] = temp;
    }
    return arrayToSort;
}

And that is the selection sort algorithm in Java. This algorithms O notation is 0(n²), as our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop, giving us n² loops. So this algorithm runs in 0(n²) also known as quadratic time because if our loop had 10 items, it would loop 100 times (10²). This is a slow algorithm, the runtime is long. But its space complexity (memory usage) is good, it is 0(1) which means the algorithm is constant.

[GitHub Repo]