Suppose the we have set of cards, now we keep all the cards in our left hand and select one smallest card and then transfer that card to our right hand, similarly we repeat the process with all other cards then we will get all sorted cards in our right hand.
Below is pictorial representation of the example.
This is the set of cards that we have kept in our left hand.
Now we are transferring the smallest cards from our left hand to right hand one by one.
You can apply this same approach in the programming. You have to notice thing that in the above example of "sorting of cards" we have used our two hands but in case of programming we have to use only one array.
We will see how we can use only a single array.
Now suppose that we have an array :
3,7,5,1,4,2
Now one way of sorting this can be selecting the smallest element from the array and strong it into another empty array and continuing the same procedure again and again. (But this will occupy extra memory space) So we will not follow this method.
Second approach:
We will look at the index of smallest element, and then we can swap that element with element of zero index. And again we can search of the minimum element and swap it with the element at index `1`. Repeat the same procedure and you will end up with a sorted array.
Algorithm of Selection Sort:
Below is pictorial representation of the example.
This is the set of cards that we have kept in our left hand.
And thus now we come up with a sorted bunch of cards in our right hand.
We will see how we can use only a single array.
Now suppose that we have an array :
3,7,5,1,4,2
Now one way of sorting this can be selecting the smallest element from the array and strong it into another empty array and continuing the same procedure again and again. (But this will occupy extra memory space) So we will not follow this method.
Second approach:
We will look at the index of smallest element, and then we can swap that element with element of zero index. And again we can search of the minimum element and swap it with the element at index `1`. Repeat the same procedure and you will end up with a sorted array.
Algorithm of Selection Sort:
SelectinSort(Array, Size)
for i <- 0 to n-2
min = i
for j = i+1 to n-1
if Array[j] < Array[min]
min = j
swap Array[i] and Array[min]
Done
Program of Selection Sort:This sorting is in ascending order.
#include<iostream>
void SelectionSort(int Array[], int size)
{
int min, flag = 0; // flag is taken to check if the value of min changes or not
for(int i = 0; i < size-2; i++)
{
min = i;
for(int j = i+1; j < size-1; j++)
{
if(Array[j]<Array[min])
{
min = j;
flag = 1;
}
}
if(flag = 1)
{
int temp = Array[i];
Array[i] = Array[min];
Array[min] = temp;
}
}
return;
}
int main()
{
int Array[100];
int Size;
std::cout<<"\n Enter the number of elements you want to sort : ";
std::cin>>Size;
std::cout<<"\n Enter the elements of array : \n";
for(int i = 0 ; i < Size; i++)
std::cin>>Array[i];
std::cout<<"\n Array before sorting is : \n";
for(int i = 0 ; i < Size; i++)
std::cout<<" "<<Array[i];
SelectionSort(Array, Size);
std::cout<<"\n The array after sorting is : \n";
for(int i = 0 ; i < Size; i++)
std::cout<<" "<<Array[i];
return 0;
}
If you have any doubt then just comment below or send an email of youarefreak1@gmail.com.
Thanks.
