Selection Sort

Selection Sort

Scan the array to find its smallest element and swap it with the first element. Then, starting with the second element scan the entire list to find the smallest element and swap it with the second element. Then starting from the third element the entire list is scanned in order to find the next smallest element. Continuing in this fashion we can sort the entire list.

Generally, on pass i (0 ≤i≤n-2), the smallest element is searched among last n-i elements and is swapped with A[i]

The list gets sorted after n - 1 passes.

Example 1:

Consider the elements

70, 30, 20, 50, 60, 10, 40

We can store these elements in array A as:

1^st pass:

2^nd pass

3^rd pass:

As there is no smallest element than 30 we will increment i pointer.

4^th pass:

6th pass:

This is a sorted array.

Let us see the complete implementation of selection sort.

Ex. 6.4.1 C Program for sorting elements using selection sort.

Sol. :

#include<stdio.h>

#include<conio.h>

int n;

void main()

{

int i,A[10];

void selection(int A[10]);

clrscr();

printf("\n\t\t Selection Sort\n");

printf("\n How many elements are there?");

scanf("%d", &n);

printf("\n Enter the elements\n");

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

scanf("%d",&A[i]);

selection(A);

getch();

}

void selection(int A[10])

{

int i,j,Min,temp;

for(i=0;i<=n-2;i++)

{

Min=i;

for(j=i+1;j<=n-1;j++)

{

if(A[j]<A[Min])

Min=j;

}

temp=A[i];

A[i]=A[Min];

A[Min]=temp;

}

printf("\n The sorted List is ...\n");

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

printf("%d",A[i]);

}

Output

Selection Sort

How many elements are there?7

Enter the elements

70

30

20

50

60

10

40

The sorted List is...

10 20 30 40 50 60 70

Review Question

1. Write an algorithm to implement selection sort with suitable example.