Counting Sort :
n is number of values in array , k is the range of values (max – min )
Compexity : O(n+k)
Counting sort is a sorting technique to sort an array in linear time. It uses an extra space for counting occurrence of each object in array. This technique is efficient when range of data is not much larger than number of inputs to be sorted.
|
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 |
/* Counting Sort Code by codingstreet.com Complexity: O(n+k); n is number of object in the array k is range of input */ #include<stdio.h> #include<stdlib.h> void printarray(int A[],int size){ int i; printf("\n "); for(i=0;i<size;i++) printf("%d ",A[i]); } void counting_sort(int A[],int size){ int min,max,i,range,*p,j; min=A[0],max=A[0]; for(i=0;i<size;i++){ if(A[i]<min) min=A[i]; if(A[i]>max) max=A[i]; } range=max-min+1; p=malloc(sizeof(int)*range); for(i=0;i<range;i++) p[i]=0; for(i=0;i<size;i++){ p[A[i]-min]+=1; } int k=0; /* First Fore loop is executed 'range' times and second while loop wil be executed only 'size' */ for(i=0;i<range;i++){ j=p[i]; while(p[i]!=0 && j!=0){ A[k]=i+min; k++; j--; } } } int main(){ int A[]={5,9,8,6,15,11,7,5,8}; int n=sizeof(A)/sizeof(A[0]); // Array Before Sorting printarray(A,n); counting_sort(A,n); // Array After counting Sort printarray(A,n); return 0; } |