**Selection sort**is a sorting algorithm, specifically an in-place comparison sort. It has O(

*n*

^{2}) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Selection sort carries out a sequence of passes over the table. At the first pass an entry is selected on some criteria and placed in the correct position in the table. The possible criteria for selecting an element are to pick the smallest or pick the largest. If the smallest is chosen then, for sorting in ascending order, the correct position to put it is at the beginning of the table. Now that the correct entry is in the first place in the table the process is repeated on the remaining entries. Once this has been repeated

*n*-1 times the

*n*-1 smallest entries are in the first

*n*-1 places which leaves the largest element in the last place. Thus only

*n*-1 passes are required. The algorithm can be described as follows:

For example consider the following example of selection sort being carried out on a sample set of data:for i from 1 to n-1 { Find smallest element in ith to nth entries. Exchange this element with ith entry. }

The algorithm is now written in C++. Of course the limits 1 to9 2 5 7 4 8 on pass 1 look for smallest in 1st to 6th swap 2nd with first giving 2 9 5 7 4 8 on pass 2 look for smallest in 2nd to 6th swap 5th with second giving 2 4 5 7 9 8 on pass 3 look for smallest in 3rd to 6th swap 3rd with third giving 2 4 5 7 9 8 on pass 4 look for smallest in 4th to 6th swap 4th with fourth giving 2 4 5 7 9 8 on pass 5 look for smallest in 5th to 6th swap 5th with 6th giving 2 4 5 7 8 9 sorted.

`n-1`

in
the above now become 0 to `n-2`

because array subscripts start at 0.
```
``````
for (i = 0; i < n-1; i++)
{
// find smallest entry in ith to n-1 th place
// p is subscript of smallest entry yet found
p = i;
for (j = i+1; j < n; j++)
if (a[j]<a[p])
p = j;
// exchange pth element with ith element
t = a[p];
a[p] = a[i];
a[i] = t;
}
```

Note that when finding the smallest element the index `p`

is the
index of the smallest value found so far. Only after the position of
the minimum value has been found does the actual interchange take
place.
In assessing the efficiency of sorting routines it is usual to count the number of comparisons made between keys and the number of exchanges of table entries.

To count the number of comparisons in the above algorithm note that the outer loop is traversed

`n-1`

times. At the `i`

th execution of
the outer loop the inner loop is executed as `j`

takes values
from `i+1`

to `n-1`

, that is `n-i-1`

times. Hence the
total number of comparisons made is
So on comparisons selection sort is order( ). Thus doubling the number of entries to be sorted will mean that four times as many comparisons will be made.(n-1)+(n-2)+.....+3+2+1 = n(n-1)/2

Inside the outer loop entries are exchanged three times. Thus the total number of exchanges is 3*(

*n*-1), i.e. of order(

*n*).

` `

Source code:

` `

```
#include "stdio.h"
void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;
for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
}
```

#include

ReplyDeleteusing namespace std;

int main()

{

int a[10]={0,26,4,9,1,52,2100,33,45,51};

int i=0,j=0,Loc=0,temp=0,Min=0;

for(j=0;j<10;j++){

Min=a[j];

for(i=j;i<10;i++)

{

if(Min>a[i])

{

Min=a[i];

Loc=i;

}

}

temp=a[j];

a[Loc]=temp;

a[j]=Min;

}

for(i=0;i<10;i++)

{

cout<<a[i]<<endl;

}

return 0;

}