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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Two Linear Sorts”

  1. Vikas Tandi said
    April 27, 2011 at 1:43 PM

    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
    April 27, 2011 at 1:46 PM

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

    free(count);
  3. Vikas Tandi said
    April 30, 2011 at 8:40 AM

    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 comment