In previous tutorial on Sorting Algorithms we have learnt aboutBubble sort Algorithms and how to use it in your code.Following that in this tutorial we are going to see about Selection sort Algorithm – how it works and how to implement this Algorithm in your code to achieve sorting.
SELECTION SORT ALGORITHM:
This Algorithm uses Linear search to find the smallest or largest number ( depends on the type of sort ) in an array.On finding the smallest element in an array in case of ascending order sort this algorithm will swap the place of that smallest number to the very initial position in the array.Now the number in the first position of the array is considered as sorted.Then this Algorithm will continue to run the linear search and find the next smallest number in array.Then the smallest number will be moved to the next position of already sorted element.Algorithm repeats the linear search and swapping of elements in the array until all the elements are sorted.
EXPLANATION:
To explain this better let's consider the below array with five numbers and our goal is to sort this in Ascending order.
Let's run a linear search to find out the smallest element in this given array.
With the help of linear search we find out that the smallest number in this array is 5
Now swap the position of 5 with 43 which is located at the first place in the array.
After swapping positions, 5 is considered to be fully sorted and will be left undisturbed henceforth.
The linear search continues to find the next smallest element in the array
With the help of linear search we now found out that 7 is the smallest number
Now position of 7 is swapped with 15 which sits in the second position of the array
5 and 7 is considered to be fully sorted in this array.
Now the linear search and swapping continues until all the numbers in the array is sorted.For the sake of simplicity I have omitted the intermittent steps and shows only the results.15 is considered to fully sorted now.
25 is considered to be fully sorted.
43 and the whole array is now fully sorted.
SELECTION SORT ALGORITHM:
These are the steps that you need to implement in your code to sort the above array in ascending order.
- Run linear search by comparing two elements at a time.
- Copy the position of smallest value into a variable with each comparison.
- Compare the smallest value with other values in the array.
- When all the values are compared we will have the position of smallest value out of all values in the array.
- Now swap the number in this position with the 0 position of the array.Now the number in 0th position is considered to be fully sorted.
- Then repeat the linear search again and fetch the position of smallest value.
- And swap the values with the 1st position of the array.
- Repeat until all the values in the array is sorted.
CODE:
The below code uses Selection sort algorithm to sort the above given array in Ascending order.
#include
int array[5]={43,15,5,25,7}!//Data in Array int main() { int i=0!int j=0!int position=0!while(i<=4) { j=i+1!while(j<=4) //Linear search for minimum values { if(array[position]>array[j]) { position=j!//Copying the position of smallest value after each comparison } j++!} int temp1, temp2!temp1=array[i]!//Swapping the values temp2=array[position]!array[i]=temp2!array[position]=temp1!i++!position=i!} int k!for(k=0;k<=4;k++) printf("%d\n",array[k])!//Printing sorted array return 0!}
WHERE TO USE SELECTION SORT ALGORITHM:
This Sorting algorithm will perform well only for small data sets and gets worse with large number of data sets.The reason behind this is that it needs to compare each and every value in the array and then sort it as you need.But on the other hand this Algorithm is quite simple to implement and doesn't need much space in memory.So use this Algorithm only when you have small number of values and to avoid writing complex lines of code.
ACTIVITY:
In order to understand this Algorithm better, practice the below activity and familiarize with it better.
- Write a program that allows user to enter the sequence of values to be sorted and then sort it in descending order using Selection sort algorithm.
I really hope this tutorial would have helped you to understand this Algorithm better.Do share the result of this activity with me.If you have any questions, feedback or comments regarding this article do post them in the comment box below.Happy coding
