Page 372, Exercise 1

The count sort uses the following struct.

typedef struct 	{
	   int key;
	   int count;} element;

The distribution count works by making N-1 passes over the data. All counts start out with a value of one. The count is incremented only if the value is truly less than the value with which it is compared. This means that the counts will match the relative order of the keys. Hence, a sort which uses these counts will be stable.

An example might illuminate count's operation.  Assume that an array consists of the following: 10, 5, 20, 15.  The function will make n-1 = 3 passes over the array.  On the first pass it will compare positions 0 & 1, 0 & 2, and 0 & 3.  On the second pass, it compares 1 & 2 and 1 & 3; and on the final passes it compares 2 & 3.  The final counts will be: 1, 0, 3, 2. These counts indicate the sorted array position of the keys.

The loop structure is commonly found in computer science.  Its complexity is O(n·(n-1)/2) ≈ O(n²).  This can be verified easily from the nested for loop structure.

The call is:

CountSort(list,n);
for (i = 0; i < n; i++)
     printf("%d\t%d\n",list[i].key, list[i].count);

void CountSort(element list[], int n)
/* count the number of elements in the array < then those in the ith
  or jth position; The element itself is given the number 1 to match
  array subscripts*/
{
  int i,j;
  for (i = 0; i < n; i++) /*set counts to 0 */ 
     list[i].count = 0;
  for (i = 0; i < n-1; i++)
  /* determine the number of keys less than each key */
     for (j = i+1; j < n; j++)
        if (list[i].key > list[j].key)
		    list[i].count++;
		 else
		     list [j].count++;
}