Initially, the entire list is unsorted but with every iteration, the smallest item in the list is searched (for ascending list) and added to the sorted section.<\/p>\n\n\n\n
How this happens is that one by one, we find the smallest item in the unsorted section and swap it with the item at its correct position.<\/p>\n\n\n\n
So in the first iteration, the smallest item is swapped with the item at the first position. In the second iteration, the second smallest item is swapped with the item at the second position. And so on…<\/p>\n\n\n\n
Implementing Selection Sort in Python<\/h2>\n\n\n\n
Below is a simple implementation of selection sort in Python. <\/p>\n\n\n
\ndef selection_sort(lst):\n n = len(lst)\n for i in range(n - 1):\n min = i\n for j in range(i + 1, n):\n if(lst[j] < lst[min]):\n min = j\n lst[i], lst[min] = lst[min], lst[i]\n<\/pre><\/div>\n\n\nNotice that the function takes in a list and performs the sorting in-place, it is fairly simple to alter the algorithm to return a sorted list instead.<\/p>\n\n\n\n
Explaining the Steps of the Selection Sort Algorithm<\/h2>\n\n\n\n
This algorithm sorts the list in increasing order, let us see how it works.<\/p>\n\n\n\n
- The variable
n<\/code> is the number of items in the list.<\/li>- Now,
i<\/code> goes from0<\/code> ton - 2<\/code>, which means thati<\/code> points from the first item to the second-last item. The role ofi<\/code> is that it will always point to where the next smallest item will go, so we will find the smallest item fromi<\/code> to the end of the list, and it will be placed ati<\/code>.<\/li>- We are considering the item at
i<\/code> to be the smallest one for now, because if we fail to find a smaller element afteri<\/code>, theni<\/code> holds the correct item.<\/li>- Inside,
j<\/code> goes fromi + 1<\/code> ton - 1<\/code>, which means thatj<\/code> will point to all the items afteri<\/code>, and it will be responsible to find the smallest item in that range.<\/li>- Now we compare the item at
j<\/code> to the smallest item we have found yet, and if the item atj<\/code> is smaller, then it becomes the smallest item we have found yet.<\/li>- After the inner loop, we have found the smallest item from
i<\/code> ton - 1<\/code>, and it is swapped with the item ati<\/code> so that it goes to its correct position.<\/li>- The outer loop will continue to select and place the next smallest items one after the other until the entire list is sorted.<\/li><\/ul>\n\n\n\n
Now we will try to dry-run this algorithm on an example and see how it affects the sequence. <\/p>\n\n\n\n
Let’s consider the sequence as 12, 16, 11, 10, 14, 13.<\/strong>
Size of the given list (n): 6<\/strong><\/p>\n\n\n\n12, 16, 11, 10<\/span>, 14, 13
10<\/span>, 16, 11<\/span>, 12, 14, 13
10<\/span>, 11<\/span>, 16, 12<\/span>, 14, 13
10<\/span>, 11<\/span>, 12<\/span>, 16, 14, 13<\/span>
10<\/span>, 11<\/span>, 12<\/span>, 13<\/span>, 14<\/span>, 16
10<\/span>, 11<\/span>, 12<\/span>, 13<\/span>, 14<\/span>, 16<\/span><\/p>\n\n\n\n- The numbers in green are the ones that have been sorted.<\/li>
- The numbers in blue are the smallest ones from the ones that are not sorted.<\/li>
- The uncolored ones are to be sorted.<\/li><\/ul>\n\n\n\n
It can be seen that the algorithm finds the smallest items and then swaps them with the item at their correct place.<\/p>\n\n\n\n
The Output<\/h2>\n\n\n\n
Running the same list on the algorithm will produce the following result:<\/p>\n\n\n\n
![\"Selection](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2021\/02\/selection-sort-example.png\")
Selection Sort in action<\/figcaption><\/figure><\/div>\n\n\n\n Conclusion<\/h2>\n\n\n\n
In this tutorial, we saw how Selection Sort works, we implemented the algorithm in Python and verified the dry-run of an example using the actual output of the code. <\/p>\n\n\n\n
- Now,