This week I decided to spend more time with algorithms and data structures. I decided I would take a look at sorting algorithms, so let’s jump in with selection sort. Selection sort is similar to bubble sort, but instead of placing the large values into a sorted position first, you place the smaller ones.
Let’s think about how we would implement selection sort in a few steps:
- Store the first element from the array as the smallest value(minimum)
- Compare the minimum to the next value in the array, looking for a smaller number.
- If a smaller number is found make that index the new minimum and continue iterating through the array.
- Once you reach the end of the array if the minimum is not the value of index you started with, swap the two values.
- Repeat the steps with the next element until the array is sorted.
Let’s say we are given this array : [10,5,3,2,6,4,3,1]
We want to first start by looping over the array and based off our pseudocode we will create a variable(min) and store the first index of the array.
Next we will create a nested loop with j, here we will compare if arr[j] is less than arr[min]. If it is, we will set min to j.
Once we iterated through the loop we create a variable called temp and set that to arr[i]. We set arr[i] to arr[min] and arr[min] to temp.
We first check to see if i is not equal to min, if it’s true we implement the temp swap above and continue through the array. Returning the sorted array.
Selection Sort does not have the best time complexity as it is 0(n²).