SELECTION SORT

SELECTION SORT

The idea of selection sort is rather simple. In this we repeatedly find the largest and smallest value in  array and place it at its final position as required for ascending or descending order.It is less efficient than insertion sort and has n2 complexity for all three cases.It is also not  much efficient for larger amount of data.

Worst Case:O(n2)

Average Case:O(n2)

Best Case:O(n2)

ALGORITHM:

• Input array as a[]
• for i=0 to i<n-1
  for j=i+1 to n
  find the smallest in between j to (n-1)th index and compare and swap it with i th index.
• Print the sorted array

e.g, To sort  5,3,2,0

 5 , 3 , 2 , 0            i=0, min=0, swap(5,0)
 0 , 3 , 2 , 5            i=1, min=2, swap(3,2)
 0 , 2 , 3 , 5            i=2, do nothing
 0 , 2 , 3 , 5            SORTED ARRAY

C SOURCE CODE:

#include<stdio.h>
#include<conio.h>   
void main() 
{ 
int a[100], n, i, j, temp;   
printf("Enter number of elements\n"); scanf("%d", &n);   
printf("Enter %d elements\n", n);   

for (i = 0;i<n; i++)
scanf("%d", &a[i]);

for(i=0;i<n-1;i++)
{
temp=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[temp])
temp=j;
}
if(temp!=i)
swap=a[i];
a[i]=a[temp];
a[temp]=swap;
}
}
}

printf("Sorted array\n");   
for (i=0;i<n;i++ ) 
printf("%d\t",a[i]);   
getch(); 
}