Selection Sort
In these section we will going to learn about Selection Sort in most efficient and in a very simple way. So, let’s dive into it.
Selection Sort:- In Selection Sort after the First Pass smallest element will be at its Sorted Position. In Selection Sort we search in the array for smallest element and swap the smallest element by first element. We denote our smallest element of array as “min”.
Now, how to find which element is smallest in array so we assume First Element as smallest element and we put first element as min.
Let’s Understand it with the help of an example-
15 9 16 1 8 3
In the Example First we keep min = 15 then we start comparing 15 with 9 if 15 is greater than 9 so, our min element become 9 now and again we compare our min elements with next element and so on. After each comparison our “min” value changes if previous value of “min” is greater than to that of new one. So,after the First Pass of selection sort our array become like (1 9 16 15 8 3). After the first pass of selection sort our smallest element is on its sorted or on its final position.
If there are n elements in our array we require (n-1) passes in selection sort. Like, there are Six Elements in our array so in first pass we require 5 comparisons.
So, our example of array is 15 9 16 1 8 3
First Pass- 1 9 16 15 8 3 (n-1 Comparison)
Second Pass- 1 3 16 15 8 9 (n-2 Comparison)
Third Pass- 1 3 8 15 16 9 (n-3 Comparison)
Fourth Pass- 1 3 8 9 16 15 (n-4 Comparison)
Fifth Pass- 1 3 8 9 15 16 (1 Comparison)
How many pass in Selection Sort:- If there are “n” elements we require (n-1) Passes.
How many Comparison by Selection Sort:-
1+2+3+ — — — — — — -+(n-3)+(n-2)+(n-1)
=n(n-1/2)
Sum of first natural no =(n-1)(n-1+1)/2
n(n-1)/2
n²-n/2
o(n²)
Swap In Selection Sort:-
Minimum no of swap = Zero [ When array is already sorted]
Maximum no of swap = (n-1) [ When array is Reverse sorted]
Now, we have basic understanding of Selection Sort now let’s dive into the code of selection sort so, we get an idea about how to implement selection sort and how can we use it.
Code for Selection Sort:-
Consider a array:- 12 6 8 5 1 7
if(a[i]<min)
min=a[i];
pos=i;
{
swap(a[i],a[pos])
}
Basic Algorithm For Understanding Selection Sort.
Void Sort(int a[], int n) {
for(j=0;j<=n-2;j++)
{
min=a[j], pos=j;
for(i=j+1;i<=n-1;i++)
{
if(a[i]<min) [We have taken pos element because we swap position of min with the element]
{
min=a[i];
pos=i;
}
swap(a[j],a[pos]);
}
}
}
Can we Modify Selection Sort:- So, For answer to these question we can say that Modified Bubble sort is modification of both Bubble sort and Selection sort.