Selection sort

Intro

Selection sort fits into the group of the slowest sorting algorithms (together with Bubble sort and Insertion sort) with the time complexity of the O(n^2).

It is one of the slowest algorithms because we need to write nested loops, just like we did in the Bubble sort. 

Selection sort - how does it work?

In Selection sort, we first select the first element in the array to be the minimum. Then we start comparing it to the other elements, and when we find an element that is smaller than the current minimum, we set that element to be the minimum and continue with iteration. 
When we finish iterating, we then swap the element that is the minimum with the arr[i] where i is the variable counter of the outer loop.

So after every iteration of the outer loop, we place the current minimum at the corresponding place, by swapping the arr[i] with the min.

Let's code it

Below is the Java code of the Selection sort

public class SelectionSort {

public void sort(int[] arr) { // O(n^2)

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

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

}
}

We used the nested loop approach because we needed to compare the elements with every other element.
At the start of each iteration of the outer loop, we set the min to be the i, the current element in the array. When we finish with iteration and comparing the elements, we just swap the current element from the outer array - arr[i], with the element at the index of min.

Note: When we know that we need to compare each element with every other element, we always need to use the nested loops.

Selection sort - analysis

For this algorithm, the worst, average, and best time complexity is O(n^2). 

Worst and Average time O(n^2)  - to find the minimum, we need to iterate through the entire array.

Best time O(n^2) - it is still the n^2, because in the case of the sorted array, we still need to traverse the entire array. Just no swaps will occur.

Space complexity is always O(1) - because we are not creating any data structure, hence no additional memory will be taken.