Sorting Algorithm
In this tutorial we will learn about Selection sort algorithm.
In this technique we find the smallest element in each pass and place it in the appropriate position to get the elements in ascending or descending order.
In pass 1, smallest element is searched between a[0] to a[n-1] and swapped with a[0].
In pass 2, smallest element is searched between a[1] to a[n-1] and swapped with a[1].
In a similar way the process is carried out n-1 times.
/** * a[0:n-1] is an array of n elements. * temp is a variable to facilitate exchange. */ SelectionSort(a,n) Begin for k = 1 to n-1 by 1 do //this is for pass Set small = a[k-1]; Set pos = k-1; for j = k to n-1 by 1 do //this is for searching small element if(a[j] < small) then Set small = a[j]; Set pos = j; endif endfor if(pos != k-1) then //swap value Set temp = a[k-1]; Set a[k-1] = a[pos]; Set a[pos] = temp; endif endfor End
#include <stdio.h> //function declaration void selectionSort(int *a, int n); int main(){ //variable declaration int arr[5], i; //input for(i = 0; i < 5; i++) scanf("%d", &arr[i]); //sort selectionSort(arr, 5); //passing arr address and no. of elements //output for(i = 0; i < 5; i++) printf("%d\n", arr[i]); return 0; } //function definition void selectionSort(int *a, int n){ int k, j, pos, small, temp; for(k = 1; k <= n-1; k++){ small = a[k-1]; pos = k-1; for(j = k; j <= n-1; j++){ if(a[j] < small){ small = a[j]; pos = j; } } if(pos != k-1){ temp = a[k-1]; a[k-1] = a[pos]; a[pos] = temp; } } }
1st pass requires (n-1) comparison 2nd pass required (n-2) comparison ... last pass requires 1 comparison.
So, total comparison = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n2)