Two Linear Sorts
November 13, 2009
It is well known that any comparison-based sort, as we have been studying, has a lower time bound of O(n log n). But if all the keys are positive integers less than or equal to n, it is possible to sort in O(n) linear time by taking advantage of the structure of the keys themselves.
Count sort determines, for each input element x, the number of elements less than x, then places x directly in its position in the output; if there are k elements less than x, then x belongs in the kth + 1 position (being careful to properly consider the case of equal elements). Count sort requires two temporary arrays, one to hold the counts of the various elements, which act as indexes into the array, and one to build up the output.
Radix sort extends count sort by making multiple passes based on the positional digits of the integers being sorted: first do a count sort on the digits in the ones column of the integers, then a count sort on the digits in the tens column, then the hundreds column, the thousands column, and so on until the input is sorted, taking advantage of the fact that count sort is stable. Radix sort works on other kinds of keys besides integers; for instance, dates can be sorted by doing count sort on day, month and year in succession.
Your task is to write functions that sort arrays using count sort and radix sort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
my implementation for count sort in c
#include <stdlib.h> /* All keys in input array are positive integers less than or equal to n */ int count_sort(int arr[], int size, int n, int output[]) { int i; int *count; /* allocate for array count */ if((count = (int*)malloc(sizeof(int) * n)) == NULL) return 0; /* set count to zero */ for(i = 0; i < n; i++) count[i] = 0; /* store the count of all keys in array count. After this operation count[i] is the number keys equal to i */ for(i = 0; i < size; i++) count[arr[i]-1]++; /* Accumulate the keys to find the position of particular key. After this operation count[i] is the number of keys that are less than and equal to i */ for(i = 1; i < n; i++) count[i] = count[i] + count[i-1]; /* moving from right to left to keep the sorting algorithm stable */ for(i = size-1; i >= 0; i--) { output[count[arr[i]-1] - 1] = arr[i]; count[arr[i]-1]--; } return 1; }forget to free count array. Add given code after line 32
My implementation of radix list sort in C
#include <limits.h> #define M 10 #define NULL 0 typedef struct element { int key; struct element* link; }elem; static int get_kth_least_significant_digit(int key, int k); elem* radix_list_sort(elem arr[], int n) { /* point to the element currently being processed */ elem *ptr; /* top[i] for 0 <= i < M point to the top element of ith the pile. bottom[i] for 0 <= i < M point to the bottom element of ith the pile. The piles actually will behave as queues */ elem *top[M], bottom[M]; /* p contain the maximum value of the maximum no. of digit possible in the key */ int p; /* current position of the digit of key. The processing will start from least significant digit to most significant digit */ int k; int max_key; /* calculate the maximum no. of digit possible in the key */ for(max_key = INT_MAX, p = 0; max_key; p++, max_key /= 10); /* set ptr to the rightmost key */ ptr = &arr[n-1]; for(k = 1; k <= p; k++) { /* j will contain the position of ptr for first pass */ int j; int r; elem *currentq; int i, digit; /* set pile empty */ for(i = 0; i < M; i++) { top[i] = &bottom[i]; bottom[i].link = NULL; bottom[i].key = 0; } for(j = n-1;; j--) { /* extract kth digit of the key */ digit = get_kth_least_significant_digit(ptr->key, k); /* adjust links */ top[digit]->link = ptr; top[digit] = ptr; if(k == 1) { if(j == 0) break; ptr = &arr[j-1]; continue; } ptr = ptr->link; if(ptr == NULL) break; } ptr = bottom[0].link; /* hook up all piles to form a single list */ for(currentq = top[0], r = 1; r < M; r++) { /* bypass all empty piles */ for(; (bottom[r].link == NULL) && (r < M); r++); if(r == M) break; currentq->link = bottom[r].link; currentq = top[r]; } currentq->link = NULL; } return bottom[0].link; } static int get_kth_least_significant_digit(int key, int k) { int divisor, i; /* generate the divisor */ for(i = 1, divisor = 1; i < k; divisor = (divisor * M), i++); key = key/divisor; return key % M; }