Learning Java after Javascript: Selection Sort


In today’s edition of Learning Java after Javascript I will be going through the Java implementation of selection sort.

Given an unsorted array, selection sort goes through the array finding the lowest value and places it at the beginning of the array, and then the second lowest, etc. The solution today will have an average time complexity of O(n²) and constant space complexity.

To start we establish a base case. If nothing is in the array we return an empty array. After that we begin to iterate through the array.

In the first for loop we start at the 0th element and only go up to the second to last element. This is because once we get to the last element there will be nothing left to compare against. We create a new variable for the index of the smallest current element which will start at the value of i. Initially I tried to store the value of the lowest element (currentLowest = array[i]) but then later realized that what I really needed was the position of that element in the array.

In the second for loop we initialize the variable j to i + 1 so that we can iterate through the remaining elements in the array to check for the lowest value available. As opposed to the previous loop this one will have to go to the last element in the array. Contained inside the loop is a simple conditional that checks to see if the value at j is less than the value at currentLowestIndex. If it is we set currentLowestIndex to the current value of j.

After finishing the ‘j’ loop we check to see if i and currentLowestIndex are equal. This is to account for the case that no smaller value was found; that the value of array[i] was already in the correct position. If they are not equal we perform a typical swap.

At the end we return the now sorted array.

Once again this algorithm is one of the more basic sorting functions and not too difficult to put together. Hope it helps!

Musician and Software Engineer following his enthusiasm