## Selection Sort:

The main idea behind the selection sort is to find the smallest entry among in a(j),a(j+1),……..a(n) and then interchange it with a(j). This process is then repeated for each value of j. Selection sort is more efficient than bubble sort and the insertion sort.

Selection sort requires (n-1) passes to sort an array. In the first pass, you will find the smallest element from a[0], a[1], a[2], … a[n-1] and swap it with the first element, i.e. a[0]. In the second pass, you will find the smallest element from a[1], a[2], a[3]….a[n-1] and swap it with a[1] and so on.

In Selection sort, the selection is performed based on keys. Hence a file with large values and small keys can be efficiently sorted with selection sort. Selection sorting does not required any additional storage.

#### Advantages:

Selection sorting does not required any additional storage. Selection sort is in-place algorithm.

#### Disadvantage:

The disadvantages of selection sorting is as the input size increases, the performance of selection sort decreases.

#### Time Complexity:

Insertion sort or the bubble sort requires exclusive swapping. Selection sorting will not require no more than n-1 interchanges. Hence there is significant decrease in run time. Its efficiency is also O(n2) for n data items.

#### Example 1: Non-recursive Selection Sort:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
/* www.troubleshootyourself.com C program to sort an array elements using Non-recursive Selection Sort */ #include<stdio.h> void selectionSort(int low, int high); int array[30]; int main() { int num, i= ; printf("Enter the number of elements: "); scanf("%d", &num); printf("\nEnter the elements:\n"); for(i=; i<num; i++) { scanf("%d", &array[i]); } selectionSort(, num - 1); printf("\nThe elements after sorting are: "); for(i=;i< num;i++) { printf("%d",array[i]); } return ; } void selectionSort(int low, int high) { int i=, j=, temp=, minindex; for(i=low;i<= high;i++) { minindex = i; for(j=i+1;j<=high;j++) if(array[j] < array[minindex]) minindex = j; temp = array[i]; array[i] = array[minindex]; array[minindex] = temp; } } |

#### Check and run the program here:

You can run this program on codeboard compiler and check the results. On the codeboard, you are also allowed to modify code and run.

#### Example 2: Recursive Selection Sort:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
/* www.troubleshootyourself.com C program to sort an array elements using recursive Selection Sort */ #include<stdio.h> int array[6] = {77, 33, 44, 11, 66}; selectionSort(int); main() { int i, n = ; printf("Array Elements before sorting: "); for (i=;i<5;i++) { printf("%d ", array[i]); } selectionSort(n); printf("\n Array Elements after sorting: "); for(i=;i<5;i++) { printf("%d ", array[i]); } } selectionSort( int n) { int k, p, temp, min; if (n== 4) { return (-1); } min = array[n]; p = n; for (k = n+1; k<5; k++) { if (array[k] <min) { min = array[k]; p = k; } } temp = array[n]; /* interchange array[n] and array[p] */ array[n] = array[p]; array[p] = temp; n++; selectionSort(n); } |

#### Check and run the program here:

You can run this program on codeboard compiler and check the results. On the codeboard, you are also allowed to modify code and run.