- Two nested loops<\/li>
- Involves swapping<\/li>
- At the end of each iteration, the lowest element is at the right position<\/li><\/ul>\n\n\n\n
Selection sort steps<\/h2>\n\n\n\n
As mentioned above, there are two loops in this algorithm. Essentially, the steps as below:<\/p>\n\n\n\n
![\"Selection](\"https:\/\/datmt.com\/wp-content\/uploads\/2022\/06\/image-2.png\")
<\/figure>\n\n\n\nLet’s consider an example to boost our understanding.<\/p>\n\n\n\n
This is the initial array:<\/p>\n\n\n\n
![\"Initial](\"https:\/\/datmt.com\/wp-content\/uploads\/2022\/06\/image-1.png\")
<\/figure>\n\n\n\nIteration 1<\/h3>\n\n\n\n
We start the outer loop at index 0, assume it’s the index with the lowest value. <\/p>\n\n\n\n
At this stage we have:<\/p>\n\n\n\n
int i =0;\nint lowest_index = 0;<\/pre><\/div>\n\n\n\n
Now compare all values from 0+1 to 4-1 (array length -1).<\/p>\n\n\n\n
Compare 1 to 3, we found that 1 < 3 so we update the lowest index<\/p>\n\n\n\n
lowest_index = 1;<\/pre><\/div>\n\n\n\n
Next we compare the next value to value at lowest_index. We found that 2 > 1 and 4 > 1 so there is no update to lowest_index needed.<\/p>\n\n\n\n
At the end of this iteration, lowest_index = 1.<\/p>\n\n\n\n
Since lowest_index != i, then we swap them.<\/p>\n\n\n\n
This is the array at the first iteration:<\/p>\n\n\n\n
![\"selection](\"https:\/\/datmt.com\/wp-content\/uploads\/2022\/06\/image-3.png\")
<\/figure>\n\n\n\nIteration 2<\/h3>\n\n\n\n
At the beginning of this iteration, the values of i and lowest_index as below:<\/p>\n\n\n\n
i =1;\nlowest_index = 1;<\/pre><\/div>\n\n\n\n
The outer loop starts at index 1 (value 3).<\/p>\n\n\n\n
The inner loop starts at index 2 (value 2).<\/p>\n\n\n\n
Now we compare value at lowest_index with values at index 2. Since 2 < 3, we update the lowest index:<\/p>\n\n\n\n
int lowest_index = 2;<\/pre><\/div>\n\n\n\n
We now compare the value at lowest_index with value at index 3 (4). Since 2 < 4, we don’t need to update the lowest index.<\/p>\n\n\n\n
Since lowest_index != i, we swap them.<\/p>\n\n\n\n
At the end of this iteration, we have:<\/p>\n\n\n\n
![\"array](\"https:\/\/datmt.com\/wp-content\/uploads\/2022\/06\/image-4.png\")
<\/figure>\n\n\n\nIt looks to us the array is sorted. However, the program doesn’t know that yet. We still need to do iteration 3.<\/p>\n\n\n\n
Iteration 3<\/h3>\n\n\n\n
i =2;\nlowest_index = 2;<\/pre><\/div>\n\n\n\n
Now we compare the value at index 3 (2 + 1 ) to the lowest index, since 3 < 4, we don’t need to update lowest_index.<\/p>\n\n\n\n
There is no value left to compare, the algorithm stops here.<\/p>\n\n\n\n
At the end of this iteration, the array looks like this:<\/p>\n\n\n\n
![\"Final](\"https:\/\/datmt.com\/wp-content\/uploads\/2022\/06\/image-5.png\")
<\/figure>\n\n\n\nSelection sort implementation<\/h2>\n\n\n\n
Here is the implementation of selection sort algorithm in Java:<\/p>\n\n\n\n