Selection sort
In this sorting first we find the smallest/ largest element then we exchange the first/ last element of the array and the smallest/ largest element we found, when we are sorting in ascending order. Next we apply the same operation on the array excluding the first/ last element. This operations goes on till (n-1) times where n is the number of elements in the array. For sorting in descending order we do the reverse of the above said operation.
Selection Sort:Let us start with an example -
23 |
-5 |
4 |
2 |
-7 |
0 |
54 |
8 |
9 |
-3 |
First two passes are given in the above figure, there will be (n-1) passes. In this case the array wolud be sorted from the end as shown by highlighting the cells.
If we choose the smallest numbers then we have to exchange with the first number and the smallest number hence the array would be sorted from the beginning.
Program-71
#include <iostream.h>
void selectionSort(int a[], int n){
In the function selectionSort()- the first loop counts number of passes. See the second loop searching for the largest number goes from 1 to n-1 (value of i is 1 first time), it starts from 1 as we have taken the zeroth element as big before the second loop starts every time. A marker k is taken which points to n-1 position initially, when at the end of second loop (every time) we find the largest number we exchange it with the number at position of k, and k points to k-1 position after every exchange takes place.The process continues till n-1 pases.
int i, j, t, k=n-1, big, pos;
for(i=1; i<=n-1; i++){
big=a[0];
pos=0;
for(j=1; j<=n-i; j++){
if(big<a[j]){
big=a[j];
pos=j;
}
}
t=a[pos];
a[pos]=a[k];
a[k]=t;
k--;
}
}
void main(){
int a[10], i;
for(i=0; i<= 9; i++){
cout<<"Enter the element :"<<i+1<<":";
cin>>a[i];
}
selectionSort(a,10);
cout<<"The sorted array is as under:\n";
for(i=0; i<=9; i++){
cout<<a[i]<<" ";
}
}