Before going to the program first let us understand what is Selection Sort?
Selection Sort:
A Selection Sort is a Sorting algorithm which finds the smallest element in the array and swaps with the first element then with the second element and continues until the entire array is sorted.
Example: Let us consider the array as given below:
The given array is sorted using Selection Sort as shown below:
Note: Red is current min.
Yellow is sorted list.
Blue is current item.
Now let us see the program code for Selection Sort and understand the code using the Explanation given below.
Program code for Selection Sort:
#include<stdio.h>
#include<conio.h> void main()
{ int a[100],n,i,j,min,temp; clrscr(); printf("n Enter the Number of Elements: "); scanf("%d",&n); printf("n Enter %d Elements: ",n); for(i=0;i<n;i++) { scanf("%d",&a[i]); } for(i=0;i<n-1;i++) { min=i; for(j=i+1;j<n;j++) { if(a[min]>a[j]) min=j; } if(min!=i) { temp=a[i]; a[i]=a[min]; a[min]=temp; } } printf("n The Sorted array in ascending order: "); for(i=0;i<n;i++) { printf("%d ",a[i]); } getch();
}
Explanation:
- First the computer reads the number of elements and stores it in the “n” variable using the following lines:
printf("n Enter the Number of Elements: ");
scanf("%d",&n);
- Then using for loop the computer reads the elements and stores it in the “a” array variable using the following lines:
printf("n Enter %d Elements: ",n);
for(i=0;i<n;i++)
{ scanf("%d",&a[i]);
}
- Then using the nested for loops it finds finds the smallest element in the array and swaps with the first element then with the second element and continues until the entire array is sorted using the following lines:
for(i=0;i<n-1;i++)
{ min=i; for(j=i+1;j<n;j++) { if(a[min]>a[j]) min=j; } if(min!=i) { temp=a[i]; a[i]=a[min]; a[min]=temp; }
}
- Finally the sorted array in ascending order is printed on the screen using the following lines:
printf("n The Sorted array in ascending order: ");
for(i=0;i<n;i++)
{ printf("%d ",a[i]);
}
Step by Step working of the above Program Code:
- Let us assume that a user enters the number of elements as “5” and the elements as “4,1,9,3,6”.
- So it assigns n=5 and stores the elements in a[]={4,1,9,3,6} using for loop.
Step for Sorting the array elements:
- Then it assigns i=0 and the loop continues till the condition of for loop is true.
3.1. i<n-1 (0<4) for loop condition is true
min=i So, min=0
Then it assigns j=i+1 (j=1) and the loop continues till the condition of for loop is true.
3.1.1. j<n (1<5) for loop condition is true
a[0]>a[1] (4>1) if condition is true
min=j So, min=1
j++ (j=j+1) So, j=2
3.1.2. j<n (2<5) for loop condition is true
a[1]>a[2] (1>9) if condition is false
j++ (j=j+1) So, j=3
3.1.3. j<n (3<5) for loop condition is true
a[1]>a[3] (1>3) if condition is false
j++ (j=j+1) So, j=4
3.1.4. j<n (4<5) for loop condition is true
a[1]>a[4] (1>6) if condition is false
j++ (j=j+1) So, j=5
3.1.5. j<n (5<5) for loop condition is false
It comes out of the for loop.
min!=i (1!=0) if condition is true
temp=a[i] (temp=a[0]) So, temp=4
a[i]=a[min] (a[0]=a[1]) So, a[0]=1
a[min]=temp (a[1]=temp) So, a[1]=4
i++ (i=i+1) So, i=1
So after first iteration the array is: 1 4 9 3 6
3.2. Similarly it continue till the value of i<4.
In each iteration the smallest element is swapped with the element of “i” in the array.
Thus after second iteration the array is: 1 3 9 4 6
After third iteration the array is: 1 3 4 9 6
After fourth iteration the array is: 1 3 4 6 9
3.3 i<n-1 (4<4) for loop condition is false
So it comes out of the for loop.
- Finally it prints the sorted array on the screen using for loop as given below:
The Sorted array in ascending order: 1 3 4 6 9
- Thus program execution is completed.
Output:
