Radix sort vs Counting sort vs Bucket sort. What's the difference?

Question

I am reading the definitions of radix, counting and bucket sorts and it seems that all of them are just the code below:

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

I know I can't be right, so what am I missing? Show the code if you think that can help explaining in Java or C.

Centrifuge

Answer 1

Let's start with some rewriting your code in C, because C more familiar for me to explain. So lets recall your code with some comments:

int
counting_sort(int a[], int a_len, int maxVal)
{
  int i, j, outPos = 0;
  int bucket_len = maxVal+1;
  int bucket[bucket_len]; /* simple bucket structure */

  memset(bucket, 0, sizeof(int) * bucket_len);

  /* one loop bucket processing */
  for (i = 0; i < a_len; i++)
    {
      bucket[a[i]]++; /* simple work with buckets */
    }

  for (i=0; i < bucket_len; i++)
    {
      for (j = 0; j < bucket[i]; j++)
        {
          a[outPos++] = i;
        }
    }

  return 0;
}

Now lets offer to this guy some realistic data:

[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]

On output we have

[126, 171, 201, 223, 316, 343, 348, 432, 556, 670]

It seems that everything is ok? Not yet. Lets look at maxVal. It is 670 (!) To sort array of 10 elements here we used array of 670 elements, primarily zeros. Awfully. To handle this problem of counting sort, we have two possible ways of generalization:

1) First way -- to make sort digit-wise. This is called radix-sort. Lets show some code, trying to make it as close to counting-sort code as possible. Again look at comments:

int
radix_sort(int a[], int a_len, int ndigits)
{
  int i;
  int b[a_len];
  int expn = 1;

  /* additional loop for digits */
  for (i = 0; i != ndigits; ++i)
    {
      int j;
      int bucket[10] = {0}; /* still simple buckets */

      /* bucket processing becomes tricky */
      for (j = 0; j != a_len; ++j)
        bucket[ a[j] / expn % 10 ]++;

      for (j = 1; j != 10; ++j)
        bucket[j] += bucket[j - 1];

      for (j = a_len - 1; j >= 0; --j)
        b[--bucket[a[j] / expn % 10]] = a[j];

      for (j = 0; j != a_len; ++j)
        a[j] = b[j];

      expn *= 10;
    }
}

We are trading multiplier near N for memory. Profit? Maybe. But in some cases multiplier near N is very important. Program, working a day and working a week are very different from users view even if both works 1*O(N) and 7*O(N) respectively. And so we are coming to a second generalization:

2) Second way -- to make buckets more sophisticated. This is called bucket-sort.

Lets again start with some code. I prefer more code prior to philosophical arguments. Still look at comments, they are essential.

int
bucket_sort(int a[], int a_len, int maxVal)
{
  int i, aidx;

  typedef struct tag_list {
    int elem;
    struct tag_list *next;
  } list_t, *list_p;

  list_p bucket[10] = {0}; /* sophisticated buckets */

  /* one loop simple processing with one more inner loop 
    to get sorted buckets (insert-sort on lists, Cormen-style) */
  for (i = 0; i != a_len; ++i)
    {
      int bnum = (10 * a[i]) / maxVal;
      list_p bptr = bucket[bnum];
      list_p belem = malloc(sizeof(list_t));
      belem->elem = a[i];
      if (bptr == 0)
        {
          bucket[bnum] = belem;
          belem->next = 0;
          continue;
        }
      else if (a[i] <= bptr->elem)
        {
          belem->next = bptr;
          bucket[bnum] = belem;
          continue;
        }
      else
        {
          while (bptr != 0)
            {
              if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
                {
                  belem->next = bptr->next;
                  bptr->next = belem;
                  break;
                }
               bptr = bptr->next;
            }
         }
    }

  /* one loop (looks as two) to get all back */
  aidx = 0;

  for (i = 0; i != 10; ++i)
    {
      list_p bptr = bucket[i];
      while (bptr)
        {
          list_p optr = bptr;
          a[aidx] = bptr->elem;
          aidx += 1;
          bptr = bptr->next;
          free(optr);
        }
    }

  return 0;
}

So what do we have here? We are trading some sophisticated bucket structure and requirement for dynamically allocated memory but winning static memory, and multiplier near N in average.

Now lets recall what did we see in code:

1. Counting sort -- simple buckets, simple processing, memory overhead
2. Radix sort -- simple buckets, sophisticated processing, speed overhead (and still need additional static memory)
3. Bucket sort -- sophisticated buckets, simple processing, requires dynamic memory, good in average

Radix and bucket sorts thus are two useful generalizations of counting sort. They have a lot in common with counting sort and with each other but in every case we are losing something and winning something. Software engineering is about a balance between these opportunities.

Katrinka

Beware that this simple hash you used for the buckets overflows for the max integer (accesses index 10). Also, it breaks if you add negative numbers. Also, it's unstable. To make it stable, the comparison in else if (a[i] <= bptr->elem) should be <. Also, while (bptr != 0), can be a while (true) – Educatory

Answer 2

Radix sort vs Counting sort vs Bucket sort. What's the difference?

Bucket sort places the keys or elements to be sorted into buckets. How they are placed in buckets is arbitrary and can be portions of a composite key and any distribution you like. The individual buckets may need to sort further.

Sorting in memory is faster than sort on disk. However if you have more data than will fit in memory you need another option. What you can do is a bucket sort, where the buckets are small enough to fit into memory. i.e. there is a large number of entries in each bucket. These you can quick sort individually.

Radix sort is a specific type of bucket sort. It starts with the top n-bit or n-digits and may sort those buckets using a radix sort etc., until every entry is sorted.

Counting sort is like using radix sort except you are using the whole value. Instead of recording each object, it has a bucket for each object and it just counts the number of occurrences. This works well when you have a limited number of possible keys and you have many duplicates.

Damalas

Answer 3

According to Geekviewpoint:

Radix: http://www.geekviewpoint.com/java/sorting/radixsort

Radix sort, like counting sort and bucket sort, is an integer based algorithm (i.e. the values of the input array are assumed to be integers). Hence radix sort is among the fastest sorting algorithms around, in theory. The particular distinction for radix sort is that it creates a bucket for each cipher (i.e. digit); as such, similar to bucket sort, each bucket in radix sort must be a growable list that may admit different keys.

Bucket: http://www.geekviewpoint.com/java/sorting/bucketsort

Bucket sort is actually very good considering that counting sort is reasonably speaking its upper bound. And counting sort is very fast. The particular distinction for bucket sort is that it uses a hash function to partition the keys of the input array, so that multiple keys may hash to the same bucket. Hence each bucket must effectively be a growable list; similar to radix sort.

Counting: http://www.geekviewpoint.com/java/sorting/countingsort

The particular distinction for counting sort is that it creates a bucket for each value and keep a counter in each bucket. Then each time a value is encountered in the input collection, the appropriate counter is incremented. Because counting sort creates a bucket for each value, an imposing restriction is that the maximum value in the input array be known beforehand.

They explain it in more details on their site.

Edit:

• If you are using radix sort and your numbers are decimal, then you need 10 buckets, one for each digit from 0 to 9.

• If you are using counting sort, then you need a bucket for each unique value in the input (actually you need a bucket for each value between 0 and max).

• If you are using bucketsort, you don't know how many buckets you will be using. Whatever hash function you are using will determine the number of buckets.

Deepsix

radix sort is similar to counting sort also because in both you must know the number of buckets before hands. – Bk

Radix sort with a radix of 10 is nonsense. One should always use a power of two as radix like 16 or 256. – Spivey

@hirschhornsalz I guess because it's a tutorial of sort, the author keeps it simple by using decimal instead of binary. – Deepsix

Answer 4

Your code is simple variant of counting sort without data, just keys.

Radix sort is sort based on this method. The problem with counting sort is memory requirement: int [] bucket=new int[maxVal+1];. Radix sort solves this problem. The idea is to use counting sort several times, first for lower digits, then for higher. For example, to sort 32-bit integers you might use:

sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key

It works, because counting sort is stable - it keeps order of data with equal keys. It's like sorting in spreadsheet: sort by B; sort by A gives you elements sorted by A, and by B when As are equal.

Bucket sort is a generalization of counting sort. You can use it to sort real numbers from some predictable probability distribution (eg. uniform (0,1)). The idea is to use counting sort (using floor(x*N_BUCKETS) as key) and then only sort each bucket independently.

Precedency

Does counting sort use both data and keys? – Incoming

@den-javamaniac - it can be used with data. You need then to remember elements of each bucket. It can be implemented with one additional array. – Precedency

Answer 5

Firstly lets look at the difference between Radix Sort and Bucket Sort because that is generally a confusing thing because the idea seems the same. Then we look at Counting Sort which is like a primary version of these two and what problems with counting sort cause the other two to be used

The initial pass of both Radix and Bucket sort are the same.The elements are put in 'Buckets' i.e 0-10, 11-20, ...and so on, depending upon the number of digits in the largest no, i.e the radix. In the next pass, however, bucket sort orders up these 'buckets' and appends them into one array. However, the radix sort method appends the buckets with-out further sorting, and 're-buckets' it based on the second digit (ten's place) of the numbers. Hence, Bucket sort is more efficient for 'Dense' arrays, while Radix Sort can handle sparse arrays well. Well think of bucket sort as this

Suppose you have a list of n records each with a key that's a number from 1 to k (we generalize the problem a little so k is not necessarily equal to n).

We can solve this by making an array of linked lists. We move each input record into the list in the appropriate position of the array then concatenate all the lists together in order.

 bucket sort(L)
    {
    list Y[k+1]
    for (i = 0; i <= k; i++) Y[i] = empty
    while L nonempty
    {
        let X = first record in L
        move X to Y[key(X)]
    }
    for (i = 0; i <= k; i++)
    concatenate Y[i] onto end of L
    }

What to do when k is large? Think about the decimal representation of a number x = a + 10 b + 100 c + 1000 d + ... where a,b,c etc all in range 0..9. These digits are easily small enough to do bucket sort.

   radix sort(L):
    {
    bucket sort by a
    bucket sort by b
    bucket sort by c
    ...
    }

or more simply

radix sort(L):
{
while (some key is nonzero)
{
    bucket sort(keys mod 10)
    keys = keys / 10
}
}

Why do we do the sort least important digit first? For that matter, why do we do more than one bucket sort, since the last one is the one that puts everything into place? Answer: If we're trying to sort things by hand we tend to do something different: first do a bucket sort, then recursively sort the values sharing a common first digit. This works, but is less efficient since it splits the problem up into many subproblems. By contrast, radix sorting never splits up the list; it just applies bucket sorting several times to the same list. In radix sorting, the last pass of bucket sorting is the one with the most effect on the overall order. So we want it to be the one using the most important digits. The previous bucket sorting passes are used only to take care of the case in which two items have the same key (mod 10) on the last pass.

Now that we have that out of the way all Counting sort does is it keeps an auxiliary array C with k elements, all initialized to 0.

We make one pass through the input array A and for each element i in A that we see, we increment C[i] by 1. After we iterate through the n elements of A and update C, the value at index j of C corresponds to how many times j appeared in A. This step takes O(n) time to iterate through A. Once we have C, we can construct the sorted version of A by iterating through C and inserting each element j a total of C[j] times into a new list (or A itself). Iterating through C takes O(k) time.The end result is a sorted A and in total it took O(n + k) time to do so.

The downfall of counting sort is that it may not be too practical if the range of elements is too large. For example, if the range of the n elements we need to sort was from 1 to n 3 , then simply creating the auxiliary array C will take O(n^3) time and counting sort will asymptotically do worse than insertion sort. This also takes O(n^3) space which is significant larger than any of space used by any other sorting algorithm we’ve learned so far. Radix sort helps solve this problem by sorting the elements digit by digit

Note: Sources for answer and further reading:

http://htmltolatex.sourceforge.net/samples/sample4.html

The first answer to: What is the difference between bucket sort and radix sort?

Couthie

Answer 6

Radix sort uses a form of counting sort as subroutine (ok, can use, but most often it will be counting sort).

Countingsort is a special form of bucket sort, as kasavbere answered.

And Bucketsort divides the keys into buckets and then sorts the buckets individually.

Stagemanage

Answer 7

To sort an array using count sort:

#define MAX_INPUT 1000

void sort(int arr[100], int n)
{
    static int hash[MAX_INPUT], i, j;

    memset(hash, 0, sizeof hash);

    for (i = 0; i < n; ++i) ++hash[arr[i]];

    j = 0;
    for (i = 0; i < MAX_INPUT; ++i)
        while (hash[i]--)
           arr[j++] = i;
}

This is just O(MAX_INPUT), thus sorting in linear time. For bucket sort, it is very different. Here is an implementation

Yippee

It does not answer the question: Radix sort vs Counting sort vs Bucket sort. What's the difference? – Surroundings

The asked just confused bucket sort with counting sort. I just showed its code to – Yippee

The running time is actually O(MAX_INPUT + n) . – Sulphurate

Ommitting n because it is relatively small comparing to MAX_INPUT (should be) – Yippee