Sorting Algorithms -Part 2
Hi I’m Lahiru Abegunawardena. This is my 2nd article on “Sorting Algorithms” topic. In 1st article of this series I described about Bubble Sorting algorithm and its implementation.
Selection Sort
Today we will discuss about selection sort algorithm. Selection sort is also follows comparison sorting algorithm. Let’s get a general idea about steps in this sorting.
In this steps you will understand that there are two parts within the list as unsorted and sorted. So basically you have to identify the smallest item in unsorted list and put it into sorted list until there are no items left in unsorted list.
Sort using Selection sort into ascending order → 8, 5, 9, 3, 6
1. → unsorted:[8, 5, 9, 3, 6], sorted:[] → smallest_value=3
2. → unsorted:[8, 5, 9, 6], sorted:[3] → smallest_value=5
3. → unsorted:[8, 9, 6], sorted:[3, 5] → smallest_value=6
4. → unsorted:[8, 9], sorted:[3, 5, 6] → smallest_value=8
5. → unsorted:[9], sorted:[3, 5, 6, 8] → smallest_value=9
6. → unsorted:[], sorted:[3, 5, 6, 8, 9]
As you can see this way it removes smallest item from unsorted part and add into end of sorted part. Even though this is the basic algorithm I have changed the process when I changed this into a java code. I’ve added some comments for a better understanding and explained code after 2nd image on selection.java
Implentation — Selection.java
Main method and printArr() function to execute the above function is given below.
I need to get your attention on first image. smlIndx index is for identifying index of smallest item in unsorted part. So as given in first for loop variable i (1st item in unsorted part) is selected as smalIndx in beginning of each iteration. Within this 2nd for loop I identify the index of smallest item in unsorted part and I exchange it with first item in unsorted part for making it easy to implement.
I printed unsorted array and 2 items to be swapped with their indexes for your understanding.
Last image given is a screenshot on execution of Selection.java class. I hope you understand code given above, however if you have any doubts or questions on any of this please don’t hesitate to contact me as given in end of this article.
Performance
Let’s look what is time complexity of this.
Worst case → O(n²) comparisons, O(n) swaps →(eg: descending order array into ascending order sort)
Best case → O(n²) comparisons, O(1) swaps → (eg: sorting already sorted array)
Average case → O(n²) comparisons, O(n) swaps
I hope you will find this article very helpful in learning about Selection sort algorithm. I would like to suggest you to try implement sorting by descending order for a better understanding on concept.
Next article will be about another sorting algorithm and its implementation or algorithm explanation. If there is anything to clarify or solve please don’t hesitate to contact me via my LinkedIn and fb page. Try all of this by yourself and if there is anything feel free to comment. Like and please Share with your friends.
