Selection Sort Using C Language and Its’ Algorithm and Complexity

In selection sort the list is traversed first time from the start to end and the lowest value is positioned in the first position. So that A[0]<=A[1].After that the list is traversed from A[1] to A[N] and the second lowest value is placed in A[1] so that the list will be A[0]<=A[1]<=A[2] and so on. N number of values will be sorted after (N-1) number of passes.

If the series is :-  77  33   44  11  88   22  66  55

After 1st pass      11  77   44   33  88   22  66  55

After 2nd  pass    11  22   77   44  88   33  66  55

After 3nd pass     11  22   33   77  88   44  66  55

After 4rth pass     11  22   33   44  88   77  66  55

After 5th Pass      11  22   33   44  55   88  77  66

After 6th Pass      11  22   33   44  55   66  77  88

After 7th Pass      11  22   33   44  55   66  77  88

Complexity of Selection Sort

There are (N-1) numbers of comparisons in the first pass, (N-2) number of comparisons in the second pass and so on. So there will be 1 comparison in the last pass.

So time complexity f(x) = (N-1) + (N-2) + (N-3) +…. +2+1

 = N (N-1)/2

 O (N2)

In both worst case and average case the complexity is O (N2)

Algorithm for Selection Sort:-

Arr represents the array of values where N is the number of elements in the array. I and J are two integer type variables. Set initial value 0 in Temp is an integer variable, will help to interchange values.

Repeat the following steps while I< N

Set J=I+1

Repeat the following steps while J< N

If  Arr[I]>Arr[J]

Temp=Arr[I]

Arr[I]=Arr[J]

Arr[J]=Temp

[End of If body]

J=J+1

[End of the inner loop]

I=I+1

[End of the outer loop]

Exit

C Language Program on Selection Sort

#include < stdio.h>

void sS(int array[], int size)

{

int temp,i,j,x=0;

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

{

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

{

  x++;

if (array[i] > array[j])

{

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

}

  printf("\nNumber of passes required:-%d",i-1);

  printf("\nTotal Number of comparisions:-%d",x);

}

void main()

{

int values[]={4,5,2,7,11,1}, i;

clrscr();

printf("\n Unsorted list is as follows \n");

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

{

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

}

sS(values, 6);

printf("\n Sorted list is as follows \n");

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

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

getch();

}

Find the total number of comparisons in worst case for a selection sort:-

Suppose there are N numbers of values in an array. So the number of comparison in the first pass will be (N-1), in the second pass it will be (N-2) and so on. So the number of comparisons will be N (N-1)/2.If the number of elements is 6, then the number of comparisons will be 6(6-1)/2, 6*5/2, 30/2, 15