Objective: C program to sort the elements using selection sort method
Concept: This uses the brute force method for sorting. In this method, obtain the first smallest number and exchange that with the element in first position. In second pass, obtain second smallest number and exchange that with second element.
ALGORITHM :
Selection sort ( A [ 0…n-1 ] )
//The algorithm sorts a given array by selection sort
//Input: An array A [ 0…n-1 ] of orderable elements
//Output: Array A [ 0….n-1 ] sorted in ascending order
Step 1: for i = 0 to n – 2 do
Step 2: min = i
Step 3: for j =i + 1 to n – 1 do
Step 4: if a[j] < a[min] then go to Step 5
Step 5: min = j
//end for
Step 6: swap A[i] and A[min]
//end for
Time complexity: n2.
Even though the time complexity of selection sort is n2, the number of swaps in each pass will be n-1, both in worst case and in best case. Observe that in worst case, selection sort requires n-1 exchanges(each pass requires one exchange) where as bubble sort requires(n-1)n/2 exchanges. This property distinguishes selection sort from other algorithms.
#include<stdio.h>
#include<conio.h>
int a[20] , n ;
void main ()
{
void selectionsort() ;
int i ;
clrscr () ;
printf ( " \n Enter size of the array : " ) ;
scanf ( "%d" , &n ) ;
printf ( " \n Enter the elements : \n " ) ;
for ( i = 0 ; i < n ; i++ )
scanf ( "%d" , &a[i] ) ;
selectionsort () ;
printf ( " \n The sorted elements are : " ) ;
for ( i = 0 ; i < n ; i++ )
printf ( "\n%d" , a[i] ) ;
getch () ;
}
void selectionsort ()
{
int i , j , min , temp ;
for ( i = 0 ; i < n - 1 ; i++ )
{
min = i ;
for ( j = i + 1 ; j < n ; j++ )
{
if ( a[j] < a[min] )
min = j ;
}
temp = a[i] ;
a[i] = a[min] ;
a[min] = temp ;
}
}
============== Output============= Enter size of the array : 5 Enter the elements : 7 1 9 3 5 The sorted elements are : 1 3 5 7 9