Selection sort in Data Structures

Selection sort

Suppose an array A with ‘n’ elements A[0],A[1],A[2]….. is in memory. The selection sort algorithm in data structures for sorting ‘A’ works as follows

Pass 1:  First find the smallest element in the list and put it into the first position. Then find the second smallest element in the list of ‘N’ elements A[0],A[1],A[2]------ and then interchange A[Loc] and A[0] is sorted.

Pass 2: Find the location LOC of the smallest in the sub list of n-1 elements A[1],A[2],A[3] then A[0],A[1] sorted

Pass N-1: Find the location LOC of the smaller of the elements A[N-1], A[N] and then interchange A[LOC] and A[N-1] then : A[0],A[1],A[2]-----  is sorted.

24

 

 Selection Sort Program

Implementation of selection sort

# include<stdio.h>

void selection sort(int a[],int n);

void main()

{

int a[20],n,i;

clrscr();

printf(“Enter n value \n”);

scanf(“%d”,&n);

printf(“Enter those numbers \n”);

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

{

scanf(“%d”,&a[i]);

}

selection sort(a,n);

printf(“Following are the elements in sorting orger: \n”);

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

{

printf(“%5d”,a[i]);

}

}

void selection sort(int a[], int n)

{

int i, min Loc, t,j;

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

{

MinLOC=i;

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

{

if(a[j]<a[minLoc])

minLoc=j;

}

t=a[i];

a[i]=a[MinLoc];

a[MinLoc]=t;

}

}

 

Time complexity :

Complexity of the selection sort algorithm

f(n)=(n-1)+(n-2)+-------- +2+1=n(n-1)/2=0(n2)

 

AlgorithmWorst capeAverage cape
selection sortn(n-1)/2=o(n2)n(n-1)/2=o(n2)

 

Output:

Enter n value : 7

Enter those numbers :

60     30     20     10     50     70     40

 

Following are the elements in the sorting order:

10     20     30     40     50     60     70