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:
/* www.troubleshootyourself.com C program to sort an array elements using Non-recursive Selection Sort */ #includevoid selectionSort(int low, int high); int array[30]; int main() { int num, i= 0; printf("Enter the number of elements: "); scanf("%d", &num); printf("\nEnter the elements:\n"); for(i=0; i 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.
How to compile and run the code on code board?You can see the codeboard compiler and editor below. If you make any changes in the code, you would need to compile the code first and run. To do that, In the codeboard editor there is a menu at the top-right corner. Click on the menu to see two buttons such as ‘Compile’ and ‘Run’ to compile and run the code respectively. Please select the filename main.c to see the code.
Example 2: Recursive Selection Sort:
/* www.troubleshootyourself.com C program to sort an array elements using recursive Selection Sort */ #includeint array[6] = {77, 33, 44, 11, 66}; selectionSort(int); main() { int i, n = 0; printf("Array Elements before sorting: "); for (i=0;i<5;i++) { printf("%d ", array[i]); } selectionSort(n); printf("\n Array Elements after sorting: "); for(i=0;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] 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.
How to compile and run the code on code board?You can see the codeboard compiler and editor below. If you make any changes in the code, you would need to compile the code first and run. To do that, In the codeboard editor there is a menu at the top-right corner. Click on the menu to see two buttons such as ‘Compile’ and ‘Run’ to compile and run the code respectively. Please select the filename main.c to see the code.