Selection sort is one of the simpler possible ways to sort a list. This algorithm works by scanning a list of items for the smallest element and then swapping that element for the one in the first position. Refer to the above image to see the smallest item seen, where it sorts based on locating the smallest item and then the next smallest item through the list in consecutive order. It keeps doing this to find the next smallest item in the list that hasn’t already been discovered.
Selection sort still has a time complexity of O(n²). It’s not very fast. Similar to bubble sort. We have nested for loops but use a time complexity of O(1). It doesn’t really add any additional data besides the input.
If you can, implement your own selection sort in simple code for the above image.
A little random extra below:
Selection sort, insertion sort, bubble sort, etc. are stable by nature. Some algorithms that are not stable include heap sort, quick sort, etc.
Just an fyi, a “stable” sorting algorithm keeps items in a list with the same sorting key in order
Insertion sort is not the most efficient algorithm but can be quick in certain circumstances. When you’re certain your list is almost sorted or completed sorted then insertion sort is pretty useful. When you have small data sets, an insertion sort algorithm can be easily implemented.
As always, I highly recommend the Zero to Mastery Academy to improve your own personal skills as a programmer as this is where all this information was drawn from and Andrei Neagoie, the founder and lead instructor, has been a true mentor to me.
Photo credit: https://courses.cs.washington.edu/courses/cse373/19au/lectures/05/reading/
