Two Linear Sorts

November 13, 2009

Count sort runs in four loops. The first loop counts the number of elements equal to i, storing the counts in the s array. The second loop sums the counts to compute the number of elements less than or equal to each i. The third loop builds the output, and the fourth loop copies the output back to the input.

function sort(A,n,    i,s,t) {
    for (i = 0; i <= n; i++) ++s[A[i]]
    for (i = 1; i <= n; i++) s[i] += s[i-1]
    for (i = n; i >= 0; i--) t[s[A[i]]--] = A[i]
    for (i = 0; i <= n; i++) A[i] = t[i] }

Count sort is repeated inline in radix sort; variable p counts the digit positions from right to left:

function digit(x,k) {
    while (k-- > 0)
        x = int(x / 10)
    return x % 10 }

function sort(A,n,    b,m,p,i,s,t) {
    for (m = 1; m <= n; m *= 10) b++
    for (p = 0; p < b; p++) {
        for (i = 0; i < 10; i++)
            s[i] = 0
        for (i = 1; i <= n; i++)
            s[digit(A[i], p)]++
        for (i = 1; i < 10; i++)
            s[i] += s[i-1]
        for (i = n; i >= 1; i--) {
            t[s[digit(A[i], p)]] = A[i]
            s[digit(A[i], p)]-- }
        for (i = 1; i <= n; i++)
            A[i] = t[i] } }

Our radix sort used count sort on decimal digits. But there is no requirement to use decimal digits; some count sorts use binary bits, and you might consider choosing the greatest integer less than or equal to the square root of n as the radix. And any other sorting method may be used in place of count sort, as long as it is stable.

The code is collected at http://programmingpraxis.codepad.org/YMEdwxX5, but you can’t run it because codepad doesn’t provide an Awk interpreter.

About these ads

Pages: 1 2

3 Responses to “Two Linear Sorts”

  1. Vikas Tandi said

    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;
    }
    
  2. Vikas Tandi said

    forget to free count array. Add given code after line 32

    free(count);
    
  3. Vikas Tandi said

    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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: