Reflections on the selection sort exercise
Selection sort is a sorting algorithm. How does it work? Let’s imagine we have the following elements to sort.
First pass: you scan through the array, pick the smallest number and place it at the beginning of the array.
Second pass: start at the second element of the array (25) and scan elements from 25 to 64. Pick the smallest number in this search range and place it after the first element you sorted. See below
Third pass: start at the third element of the array. Scan from 25 to 64. Pick the smallest number in this search range and place it after the second element in the array.
We repeat the same routine for the 4th element and the 5th element.
I spent a day working on it. I first started reflecting on the different combinations of elements in the array I should have in order to write the algorithm progressively. I wrote some tests that successfully passed until I got stuck. Below is where I stopped.
Reflection: We want to sort [3,1,2]. If I follow the selection sort process: at the first pass, I pick [1] because it’s the smallest number and I place it at the beginning of the array. The beginning of the array is [3], so I swap [1] with [3]. The array now looks like that [1,3,2].
The next step is to do a second pass. This time instead of looking at the whole array, we start looking for the second element in the array, the “new” search range is [3,2]. But how do you achieve that? How do you tell the computer to look at [3,2]. This is where I got stuck.
- First thought: let’s compare [3] and [2] and if [3] is greater than [2] then swap [2] and [3] to have [1,2,3].
→ problem: this way of sorting looks like the bubble sort algorithm and I feel bad doing it because I feel I’m not on the right path to write the selection sort algorithm.
- Second thought: there are not many ways to sort two adjacent elements. So maybe my first thought was the right one.
→ I added if statements and a while loop but I didn’t manage to make the tests pass. I also didn’t like doing it because I felt I was taking big steps and I was probably missing something along the way.
- Post exercise reflections:
→ maybe I shouldn’t have used the swapping technique to sort adjacent element. What about the append method? I’m pretty sure something like that exist. Maybe something to look up next time I’m working on the selection sort exercise.
→ Once I will figure out how to move sorted elements, I also need to figure out how to tell the computer that after each pass, he has to start looking for the smallest number of the array after the first element he just sorted. Like in this example below where after sorting 11, we start looking from 25 to 64 for the smallest number of the array.