Selection Sort

Selection sort is a sorting algorithm that passes through the unsorted part of an array to find the lowest or smallest element and puts it at the beginning. The selection sort algorithm has two subarrays. One is the sorted subarray or the part that is known to be in order. The other is the unsorted subarray or the subarray that is not yet sorted. The algorithm looks for the lowest element in the unsorted array and puts it at the beginning of that subarray. In the next pass, the first element in the unsorted subarray becomes the last element in the sorted subarray.

Example

Sort the given array {5, 1, 4, 3, 2}.

To start compare 5 to the rest of the array. 1 is less than 5 so we will track 1 as the lowest value. 4 is less than 5 but 4 is not less than the lowest value so we move on. This is repeated on the numbers 3 and 2 which are less than 5 but not less than 1. After checking all the elements in the array we will switch the 5 with the lowest value 1.

Now we start again at the second value in the array. If we go through the process of comparing the values and saving the lowest value we will find that this time the lowest value is 2. We will swap the 5 with the 2.

Starting at the third element we will again go through and find the lowest value. Once it is found we will swap it for the third element in the array.

We will run through one more time to complete the check. This time the list is already in order so nothing will change.

This algorithm has a time complexity of O(n²).

Code Implementation

To implement this algorithm you will create a function that will take an int array and the size of that array as parameters.

In this function, you will have a for loop to go through the array. You will also create a variable to track the lowest element in the array.

You will then create a nested for loop to search through the elements in the array. If the element you are at is lower than the lowest value, you will set the current element to the lowest value.

After the nested for loop is done you will swap the lowest value with the current element the first for loop is on.

We can test this in the main function by running it to get an array sorted in ascending order.

This is the full script with some extra swap and print array functions.