In this lesson, I will show you the program code for selection sort. Selection sort is one of the most easiest sorting algorithm and the codes are start forward. So, let’s get started.

Given an array *a* of *n* numbers, selection sort works by finding the minimum number and then swap it with ** a[0]**. Now that, the first number of the array is in its right place, in the second iteration, the next smallest number is found out and then swapped with

**. This process continues till the iteration step has reached the last but one step where the program terminates. The result is a sorted array.**

*a[1]*

The following is the C program code for selection sort. Viewers are advised to write the driver program themselves.

void selectionSort(int *a, int n){ //accepts an array and the size of array as parameters int i,j,indexofSmall, temp; for(i=0;i<n-1;i++){ //this for loop traverses through last but one element of the array indexofSmall = i; //the index of the initial smallest element is the first element j = i+1; while(j<n){ //while loop will identify the smallest element if(a[j]<a[indexofSmall]){ indexofSmall = j; //update the index of smallest element } j++; } //swap the smallest element with the element under consideration temp = a[indexofSmall]; a[indexofSmall] = a[i]; a[i] = temp; } return; }

**Time Complexity Analysis**

For the first iteration of the *for* loop, i.e. *i=0*, the *while* loop iterates for *n-1* times, i.e from *j=1 to j=n-1*. For the second iteration of *for* loop, i.e. *i=1*, the while loop iterates for *n-2* time, i.e from *j=2 to j=n-1*.

This continues till the while loop finishes in just one iteration i,e *j=n-1 to n-1*. Therefore, the following table makes sense. Here we have assumed that each line of code takes a constant time * c* to execute. The size of the input is

*.*

**n**

Code | Number of Iterations |
---|---|

int i,j,indexofSmall, temp; | c |

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

indexofSmall = i; | c(n-1) |

j = i+1; | c(n-1) |

while(j<n) | c*[(n-1)+(n-2)+(n-3)+. . .1]+c |

if(a[j]<a[indexofSmall){ | c*[(n-1)+(n-2)+(n-3)+. . .1] |

indexofSmall = j;} | c*[(n-1)+(n-2)+(n-3)+. . .1] |

j++; | c(n-1) |

} //while loop ends | |

temp = a[indexofSmall]; | c(n-1) |

a[indexofSmall] = a[i]; | c(n-1) |

a[i] = temp; | c(n-1) |

} |

The highest order term in the above figure will be from c*[(n-1)+(n-2)+(n-3)+. . .1], which evaluates to

$$c*[(n-1)+(n-2)+(n-3)+. . .1] = c*\frac{(n-1)n}{2} = O(n^{2}) = \Theta(n^{2})$$

As you can see, this is the best as well as the worst case time complexity of insertion sort.

The minimum as well as the maximum number of swaps that will take place in this algorithm is ** n**. The comparisons performed is in order of

**n**^{2}Kindly report any error in the comment section below.

\[\]