How do the functions work?

Question

Could you explain me how the following two algorithms work?

int countSort(int arr[], int n, int exp)
{
    int output[n]; 
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;
    for (i = 1; i < n; i++)
        count[i] += count[i - 1];
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%n] - 1] = arr[i];
        count[(arr[i]/exp)%n]--;
    }
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}


void sort(int arr[], int n)
{
    countSort(arr, n, 1);
    countSort(arr, n, n);
}

I wanted to apply the algorithm at this array:

After calling the function countSort(arr, n, 1) , we get this:

When I call then the function countSort(arr, n, n) , at this for loop:

for (i = n - 1; i >= 0; i--)
{
    output[count[ (arr[i]/exp)%n] - 1] = arr[i];
    count[(arr[i]/exp)%n]--;
}

I get output[-1]=arr[4].

But the array doesn't have such a position...

Have I done something wrong?

EDIT:Considering the array arr[] = { 10, 6, 8, 2, 3 }, the array count will contain the following elements:

what do these numbers represent? How do we use them?

Answer 1

Counting sort is very easy - let's say you have an array which contains numbers from range 1..3:
[3,1,2,3,1,1,3,1,2]

You can count how many times each number occurs in the array:
count[1] = 4
count[2] = 2
count[3] = 3

Now you know that in a sorted array,
number 1 will occupy positions 0..3 (from 0 to count[1] - 1), followed by
number 2 on positions 4..5 (from count[1] to count[1] + count[2] - 1), followed by
number 3 on positions 6..8 (from count[1] + count[2] to count[1] + count[2] + count[3] - 1).

Now that you know final position of every number, you can just insert every number at its correct position. That's basically what countSort function does.

However, in real life your input array would not contain just numbers from range 1..3, so the solution is to sort numbers on the least significant digit (LSD) first, then LSD-1 ... up to the most significant digit.
This way you can sort bigger numbers by sorting numbers from range 0..9 (single digit range in decimal numeral system).
This code: (arr[i]/exp)%n in countSort is used just to get those digits. n is base of your numeral system, so for decimal you should use n = 10 and exp should start with 1 and be multiplied by base in every iteration to get consecutive digits.
For example, if we want to get third digit from right side, we use n = 10 and exp = 10^2:
x = 1234, (x/exp)%n = 2.

This algorithm is called Radix sort and is explained in detail on Wikipedia: http://en.wikipedia.org/wiki/Radix_sort

Answer 2

It took a bit of time to pick though your countSort routine and attempt to determine just what it was you were doing compared to a normal radix sort. There are some versions that split the iteration and the actual sort routine which appears to be what you attempted using both countSort and sort functions. However, after going though that exercise, it was clear you had just missed including necessary parts of the sort routine. After fixing various compile/declaration issues in your original code, the following adds the pieces you overlooked.

In your countSort function, the size of your count array was wrong. It must be the size of the base, in this case 10. (you had 5) You confused the use of exp and base throughout the function. The exp variable steps through the powers of 10 allowing you to get the value and position of each element in the array when combined with a modulo base operation. You had modulo n instead. This problem also permeated you loop ranges, where you had a number of your loop indexes iterating over 0 < n where the correct range was 0 < base.

You missed finding the maximum value in the original array which is then used to limit the number of passes through the array to perform the sort. In fact all of your existing loops in countSort must fall within the outer-loop iterating while (m / exp > 0). Lastly, you omitted a increment of exp within the outer-loop necessary to applying the sort to each element within the array. I guess you just got confused, but I commend your effort in attempting to rewrite the sort routine and not just copy/pasting from somewhere else. (you may have copied/pasted, but if that's the case, you have additional problems...)

With each of those issues addressed, the sort works. Look though the changes and understand what it is doing. The radix sort/count sort are distribution sorts relying on where numbers occur and manipulating indexes rather than comparing values against one another which makes this type of sort awkward to understand at first. Let me know if you have any questions. I made attempts to preserve your naming convention throughout the function, with the addition of a couple that were omitted and to prevent hardcoding 10 as the base.

#include <stdio.h>

void prnarray (int *a, int sz);

void countSort (int arr[], int n, int base)
{
    int exp = 1;
    int m = arr[0];
    int output[n]; 
    int count[base];
    int i;

    for (i = 1; i < n; i++)                 /* find the maximum value           */
        m = (arr[i] > m) ? arr[i] : m;

    while (m / exp > 0)
    {
        for (i = 0; i < base; i++)
            count[i] = 0;                   /* zero bucket array (count)        */

        for (i = 0; i < n; i++)
            count[ (arr[i]/exp) % base ]++; /* count keys to go in each bucket  */  

        for (i = 1; i < base; i++)          /* indexes after end of each bucket */
            count[i] += count[i - 1];

        for (i = n - 1; i >= 0; i--)        /* map bucket indexes to keys       */
        {
            output[count[ (arr[i]/exp) % base] - 1] = arr[i];
            count[(arr[i]/exp)%n]--;
        }

        for (i = 0; i < n; i++)             /* fill array with sorted output    */
            arr[i] = output[i];

        exp *= base;                        /* inc exp for next group of keys   */
    }    
}

int main (void) {

    int arr[] = { 10, 6, 8, 2, 3 };
    int n = 5;
    int base = 10;

    printf ("\n The original array is:\n\n");
    prnarray (arr, n);

    countSort (arr, n, base);

    printf ("\n The sorted array is\n\n");
    prnarray (arr, n);

    printf ("\n");

    return 0;
}

void prnarray (int *a, int sz)
{
    register int i;
    printf ("  [");
    for (i = 0; i < sz; i++)
        printf (" %d", a[i]);
    printf (" ]\n");
}

output:

$ ./bin/sort_count

 The original array is:

  [ 10 6 8 2 3 ]

 The sorted array is

  [ 2 3 6 8 10 ]