In this tutorial I will explain about algorithm for selection sort in C and C++ using program example.
One of the simplest techniques is a selection sort. As the name suggests, selection sort is the selection of an element and keeping it in sorted order. In selection sort, the strategy is to find the smallest number in the array and exchange it with the value in first position of array. Now, find the second smallest element in the remainder of array and exchange it with a value in the second position, carry on till you have reached the end of array. Now all the elements have been sorted in ascending order.
Algorithm for Selection Sort in C & C++
Let ARR is an array having N elements
1. Read ARR
2. Repeat step 3 to 6 for I=0 to N-1
3. Set MIN=ARR[I] and Set LOC=I
4. Repeat step 5 for J=I+1 to N
5. If MIN>ARR[J], then
(a) Set MIN=ARR[J]
(b) Set LOC=J
[End of if]
[End of step 4 loop]
6. Interchange ARR[I] and ARR[LOC] using temporary variable
[End of step 2 outer
loop]
loop]
7. Exit
Program for Selection Sort in C
#include<stdio.h>
int main()
{
int i,j,n,loc,temp,min,a[30];
printf("Enter the number of elements:");
scanf("%d",&n);
printf("\nEnter the elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
}
}
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
printf("\nSorted list is as follows\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
Program for Selection Sort in C++
#include<iostream>
using namespace std;
int main()
{
int i,j,n,loc,temp,min,a[30];
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
}
}
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
cout<<"\nSorted list is as follows\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Complexity for Selection Sort in C & C++
The time complexity for selection sort program in C and C++ for both worst case and average case is O (n2) because the number of comparisons for both cases is same.
Hello, could you please tell me, why is a[30] made instead of a[n]? Isn't that array size limitation? Thanks.
Yes you can use a[n] also, but for that n must already have some value.
Thanks. I have another question ( I really want to understand this program 😀 ) why is n-1 used instead of n in for(i=0;i<n-1;i++) ? I've tested it with just n used – works fine
program works but n-1 indicates the last index value of your written array.
if ur program has array limit to 5(that is n=5) thn ur index is 0,1,2,3,4 (u got 5) so the program checks only to that limit ..
Thank you for explaining that. I was racking my brains out to understand that.?
Actually that just puts another loop to the program even though there is no use of it.When u sort the others the last one is automatically sorted so no need to sort it. It just makes the program longer.
As our index starts from 0 and the value of n will start from 1 so using n-1 we are trying to comparile index 0 from index 1 initially and proceed further with the help of loop to compare the remaining.
Hope u got that.
how to write it in descending selection sorting
just change the “>” symbol to “<" in the if statement
or replace the if statement with
if(min<a[j]); statement
hi, can you help me.. how we want to do the library for arrayListType.h . can you give me the idea .. thank you
Hey can u please tell me why do we have to use that loc variable, can’t we just swap them using min only
for swapping the values of array we need index, loc is used to store the location of min value
can u explain {min=a[i]; loc=i;}
When I use the min
The compiler says reference to ‘min’ is ambiguous
[note]candidates are:int min
Help
Which code snippet plugin you used for your code?
How we do for character element sorting
Thank you so much for this program.. doing great work. thank you!
Can any body help me writing a programe that implement all sorting algorithms together
what will we do if we want to call two selection sort functions in the body. one for descending and other one for ascending?