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; } |
C code to find out Kth smallest element in array .
Approach 1:
Sort the array using any sorting method and return the value of kth index.
Approach 2:
Using partition function of quick sort which return the index of the pivot value.
comparing the returning value from partition function with k.
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 |
/* C code to find Kth smallest element in array */ #include<stdio.h> int partition(int A[],int,int ); void swap(int *a,int *b){ int t=*a; *a=*b; *b=t; } /* n is total no of element in array , k is for kth smallest element */ int kthsmallest(int A[],int n, int k){ int i=0,flag=0; int p,q,r; p=0; r=n-1; k--; while(!flag){ q=partition(A,p,r); if(q==k) flag=1; else if(k<q){ r=q-1;} else {p=q+1;} } return A[k]; } int partition(int A[],int p,int r){ int i,j,pivot; i=p-1; pivot=A[r]; for(j=p;j<r;j++){ if(A[j]<pivot){ i++; swap(&A[j],&A[i]); } } swap(&A[i+1],&A[r]); return i+1; } int main(){ int Arr[]={5,-4,3,-2,1}; int result; result=kthsmallest(Arr,5,2); printf(" %d ",result); return 0; } |
Algorithm: Bubble Sort
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/*bubble sort on array by codingstreet.com */ #include<stdio.h> void swap(int *p,int *q){ int t; t=*p; *p=*q; *q=t; } void bubblesort(int A[],int size){ int i,j; for(i=0;i<size;i++){ for(j=size-1;j>=i+1;j--){ if(A[j]<A[j-1]) swap(&A[j],&A[j-1]); } } } int main(){ int A[]={9,8,7,6,5,4},i; bubblesort(A,6); for(i=0;i<6;i++) printf(" %d ",A[i]); return 0; } |
Algorithm: Quick Sort on Array
Complexity : Average case O(n logn) , worst Case O(n^2)
Code:
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 |
/* Quick Sort on Array code from CodingStreet.com*/ #include<stdio.h> void swap(int *p,int *q){ int t; t=*q; *q=*p; *p=t; } int partition(int [],int ,int); void quicksort(int A[],int p,int r){ int q; if(p<r){ q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } int partition(int A[],int p,int r){ int x,i,j; x=A[r]; i=p-1; for(j=p;j<r;j++){ if(A[j]<=x){ i=i+1; swap(&A[i],&A[j]); } } swap(&A[i+1],&A[r]); return i+1; } int main(){ int i,A[]={99,98,97,96,95}; quicksort(A,0,4); for(i=0;i<5;i++) printf("%d ",A[i]); return 0; } |
Quick sort on array.
Algorithm : Heap Sort on Array
Complexity :O(n logn)
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 54 |
/* Heap Sort on array code from Codingstreet.com */ #include<stdio.h> void swap(int *p,int *q){ int t; t=*q; *q=*p; *p=t; } int parent(int i){ return i/2;} int left(int i){ return 2*i;} int right(int i){ return 2*i+1;} void max_heapify(int A[],int i,int *hs){ int l,r,largest; int hsize=*hs; l=left(i); r=right(i); if(l<=hsize && A[l]>A[i]) largest=l; else largest=i; if(r<=hsize && A[r]>A[largest]) largest=r; if (largest!=i){ swap(&A[i],&A[largest]); max_heapify(A,largest,hs); } } void build_max_heap(int A[],int *hs){ int heapsize=*hs; int i,length=heapsize; for(i=length/2;i>=0;i--) max_heapify(A,i,hs); } void heapsort(int A[],int *hsize){ build_max_heap(A,hsize); int length=*hsize; int i; for(i=length;i>=1;i--){ swap(&A[i],&A[0]); *hsize=*hsize-1; max_heapify(A,0,hsize); } } int main(){ int i=5,A[]={55,50,59,33,62,1}; heapsort(A,&i); for(i=0;i<6;i++) printf("%d ",A[i]); return 0; } |
Heap sort in Array code in C .
Algorithm : Insertion Sort on array
Complexity : O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
/* Insertion Sort on array Code by codingstreet.com */ #include<stdio.h> void insertionsort(int A[],int size){ int i,j,key; for(j=1;j<size;j++){ key=A[j]; i=j-1; while(i>=0 && A[i]>key){ A[i+1]=A[i]; i=i-1; } A[i+1]=key; } } int main(){ int i,A[5]={99,95,45,10,6}; insertionsort(A,5); for(i=0;i<5;i++) printf("%d ",A[i]); return 0; } |
Insertion sort on array code in C .
Complexity : O(n2)
Explanation:
Below code picks a cell one by one and compares with each other cells , if value of current cell is greater than other cell then it will swap with other value. Similarly it performs untill picked cell is last cell.
Code :
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 |
#include<stdio.h> int main(){ int arr[100]; int size,i,j,temp; printf("n Enter the size of array to be taken input [max 100]: "); scanf("%d",&size); printf("n"); // A loop for input array for(i=0;i<size;i++){ printf("Enter the Element No %d : ",i+1); scanf("%d",&arr[i]); } // A loop for printing array printf("n Array Befor sortiong :n"); for(i=0;i<size;i++) printf(" %d ",arr[i]); // General sorting algorithm Complexity O(n^2) for(i=0;i<size;i++){ for(j=0;j<size;j++) { if(arr[i]<arr[j]) { temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } } printf("n Array After sortiong :n"); for(i=0;i<size;i++) printf(" %d ",arr[i]); return 0; } |
A place to brush your coding skills