Selection sort in c programming language:-
The selection sort consists of a selection phase in which the smallest of the remaining elements, 'small', is repeatedly placed from its position 'Minindex' in the current pass to 'index' position from the beginning of the array. To start the sorting process initially 'index'=0. We go through the list and locate the smallest element in the current list. The position of smallest element is given by'Minindex'. The smallest element at position'Minindex'is interchanged with the current element at position 'index'. Initially all elements are considered and the list is reduced by one after each selection
Pictorial representation:-
Pass 1:- Consider the list with Number of elements N=7 as below. Initially index=0
Go through the list from index=1 and for pass 3 start from index =2.
Total Number of passes for N=7 required are=N - 1 = 6.
Total Number of exchanges required are=4.
Number of passes required is always same as N -1. The total comparison in each pass are ( N-1),(N-2),(N-3),....1.
Selection sort Time Complexity
- In the worst case, in every iteration, we have to traverse the entire array for finding min elements and this will continue for all n elements. Hence this will perform n^2 operations in total.
- In the best case that is sorted array, we can do some modification by using lag to check whether the lament is already sorted or not
- Best Time Complexity: O(n)
- Average Time Complexity: O(n^2)
- Worst Time Complexity: O(n^2)
Selection sort Space Complexity
- No auxiliary space is required in Selection Sort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements
- Hence space complexity is: O(1)
Algorithm for Selection Sort Method:
- Start
- Pass -1
- i=0
- j=j+1
- if [2(i)> 3(i)]. Interchange x[i]& x[i]
- j = j+1
- If I< =n-1. Go to stepe5
- Pass = pass +1
- If pass <= n-1
10. Stop
Program for selection sort:
#include<studio.h>
#include<conio.h>
Void main()
{
int a[5], i,j,n,temp,pass;
Clrscr ();
Printf ("enter no of elements")
Scanf("%d",&n)
Printf ("enter integers:");
for (i=0: i<n; I++)
{
Scanf ("%d", & a[I];
}
for (i=1; I<n; I++);
{
for (I =j+1; j<n; j++)
{
If (a[I] > a[j] )
temp = a[I];
a[I] = a[<j];
a[j] = temp;
}
}
for ( i=0;I<n-1; I++)
{
for(i=0; i<n ; I++)
{
printf ("%d \n", a[i]);
}
fetch();
}
}
Enter no. of elements: 4
enter integers
2
1
0
3
Sorted array
0
1
2
3
