Sorting Algorithm
In this tutorial we will be learning about Counting sort algorithm.
It is a sorting algorithm in which we sort a collection of elements based on numeric keys. In this algorithm we don't compare elements while sorting. It is often used as a subroutine in other sorting algorithm.
#include <stdio.h>
//const
#define MAX 10
//function declaration
void display(int arr[], int size);
int getMax(int arr[], int size);
void countingSort(int arr[], int size);
int main() {
//unsorted elements
int arr[] = {10,15,1,60,5,100,25,50};
//size of the array
int n = sizeof(arr)/sizeof(arr[0]);
//output unsorted elements
display(arr, n);
//sort the elements
countingSort(arr, n);
//display sorted elements
display(arr, n);
return 0;
}
void display(int arr[], int size) {
int i;
for(i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int getMax(int arr[], int size) {
int i, max = arr[0];
for(i = 1; i < size; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countingSort(int arr[], int size) {
int i, max, temp[MAX], count[10], expo = 1;
//get the max value element in the unsorted array
max = getMax(arr, size);
while(max / expo > 0) {
//reset count
for(i = 0; i < 10; i++) {
count[i] = 0;
}
//save count of the occurrence
for(i = 0; i < size; i++) {
count[ (arr[i] / expo) % 10 ]++;
}
//set count to contain the actual position of the digits
for(i = 1; i < size; i++) {
count[i] += count [i - 1];
}
//build the result
for(i = size - 1; i >= 0; i--) {
temp[ count[ (arr[i]/expo) % 10 ] - 1] = arr[i];
count[ (arr[i]/expo) % 10 ]--;
}
//copy the result to arr
for(i = 0; i < size; i++) {
arr[i] = temp[i];
}
//increase expo, 10^x
expo *= 10;
}
}
ADVERTISEMENT