Let’s remind ourselves of the pseudo-code for our selection sort algorithm:
selectionSort(array)
repeat (size - 1) times
start at the beginning index of the unsorted sub-list as the current minimum
walk through all elements of the unsorted sub-list to find the index of the smallest element and set as current minimum
swap that element with the first element in the unsorted sub-list. That element is now part of the sorted sublist
end selectionSort
In this implementation of selection sort, we will write a for
loop that runs the length of the input array minus 1
.
Step 1: Inside of the for
loop we will set the current minimum index to the first position of the unsorted sub-list.
Step 2: We will look through the remainder of the unsorted sub-list to find the actual minimum index.
Step 3: We will swap the actual minimum index value with the first unsorted position and now consider that position as part of the sorted sub-list.
Step 4: We move on to the next unsorted item in the array and repeat steps 2 and 3.
Step 5: We will continue to do this until we arrive at the last element in the list.
For this exercise, we will focus on the outer for
loop iterating through our input array and setting the currentMinimumIndex
.
selectionSort(array)
...
repeat (size - 1) times
start at the beginning index of the unsorted sub-list as the current minimum
...
end selectionSort
Instructions
Inside of our selectionSort()
function, create a variable size
of type int
and set to the length of our input array.
To start sorting, we need to write a for
loop that begins with a counter, i
, initialized to 0
.
If we have a list of size 5, we know that we need to find the smallest value 4 times (the 5th smallest value will already be sorted by default). Therefore, we want our outer for loop to run 4 times. Since our loop counter is starting at 0, we want it to end once it gets to 4. The condition is therefore i < size - 1
.
Inside of our for
loop, create a variable currentMinimumIndex
of type int
and assign it the value of i
. Ultimately, we want to find the location of the smallest value in our unsorted sub-list and assign it to currentMinimumIndex
.