Counting Sort vs Radix Sort vs Bucket Sort

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

This article compares counting sort, radix sort, and bucket sort with important points that will help you make out the differences between these sorting algorithms.

Table of content:

  1. Basics of 3 different sorting algorithms
  2. Differences between Counting Sort, Radix Sort and Bucket Sort
    2.1. Time Complexity
    2.2. How they work?
    2.3. Implementation
    2.4. Other important points

Basics of 3 different sorting algorithms

Counting Sort

Counting sort is a non comparison based linear time sorting algorithm for cases where the input elements are in a limited range, usually with a given maximum limit.

Radix Sort

Radix sort is algorithm like counting sort is a linear time sorting algorithm if your data is within a limited range.

Bucket Sort

Bucket sort is a sorting algorithm which works in linear time when the data is uniformly distributed acorss a range.

Differences between Counting Sort, Radix Sort and Bucket Sort

Time Complexity:

  • The time complexity for counting sort is linear only when the range limit is linear. The time complexity is Θ(n + k) where n is the range limit and k represents the time to traverse the original array.

  • Radix sort works in linear time even if the range of the data is exponential. Assuming we have d digits as our maximum.The time complexity will beΘ(d*(n + b)) where b is the base and n the is the number of elements.

  • In comparison with radix sort and counting sort, bucket sort works in linear time and is the better algorithm when the data is perfectly distributed across a range. Bucket sort has a time complexity of Θ(n). Assuming k is approximately equal to n. In this case, k is the number of buckets and n is the number of items in the input array.

How they work:

  • In Counting sort the count of the elements is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

  • Radix sort first sort elements by grouping digits of the same place and subsequently sort the elements according to their required order, either by increasing or decreasing order.

  • The Bucket sort algorithm first divides the unsorted array elements into groups of buckets and then sorts the elements int the bucket using a sorting algorithm of choice.

Implementation:

  • Implementation of Counting sort in Java
void countSort(originalArray, originalArraySize, rangeLimit){
        int count[] = new int[rangeLimit + 1];
        int sorted[] = new int[originalArraySize.length];
        for(int i = 0; i < originalArraySize.length; i++){
            count[arr[i]]++;
        }   
        int index = 0; 
        for(int i = rangeLimit; i > =0; i--){
            int score = count[i];
          for(int j =0; j < score;j++){
            sorted[index] = i;
            index++;  
              }
        }
       
  }
  • Implementation of Radix sort in Java
void radixSort(int arr[], int n){
    int max = arr[0];
    for(int i=1; i&lt;n; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    for(int exp = 1; max/exp>0; exp *=10){
        countingSort(arr,n,exp);
    }
}
void countingSort(int arr[], int n, int exp){
    int []output = new int[n];
    int []count = new int[10];
    for(int i = 0; i < n; i++){
        count[(arr[i]/exp)%10]++;
        }
    for(int i=1; i < 10; i++){
        count[i] += count[i - 1];
    }
    for(int i = n-1; i >= 0; i--){
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    for(int i =0; i < n; i++){
        arr[i] = output[i];
    }
}
  • Implementation of Bucket sort in Java
void bucketSort(int arr[], int k){
    //k is the number of buckets
    int n = arr.length;
    int max_val = arr[o];
    for(int i =1; i < n; i++){
        max_val = Math.max(max_val,arr[i]);
        max_val++;
        }
    ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
    for(int i = 0; i < k; i++){
        bucket.add(new ArrayList<Integer>());
    }
    for(int i=0; i < n; i++){
        int bucketI =(k * arr[i]/max_val;
        bucket.get(bucketI).add(arr[i]);
    }
    for(int i = 0; i < k; i++){
        Collections.sort(bucket.get(i));
    }
    int index = 0;
    for(int i=0; i < k; i++){
        for(int j=0; j < bucket.get(i).size().j++){
        arr[index++] = bucket.get(i).get(j);
        }
    }
}

Other important points:

  • Radix sort uses counting sort as a sub routine to sort elements.
  • The time complexity of bucket sort depends on the time complexity of the chosen subroutine sorting algorithm.
  • Radix sort better than counting sorting when the range is greater than linear.
  • Counting sort is a stable linear sorting algorithm.
  • Radix sort, counting sort and bucket.
  • Counting sort cannot be used to sort a linked list.
  • Bucket sort on the other hand can be used to sort a linked list.

For a quick recap, what is the time complexity of Counting Sort?

(a) O(n + k)
(b) O(d*(n + b))
(c) O(n^2)
(d) O(nlogn)

What is the time complexity of Radix Sort?

(a) O(n + k)
(b) O(d*(n + k))
(c) O(n^2)
(d) O(nlogn)

What is the time complexity of Bucket Sort?

(a) O(n)
(b) O(d*(n + k))
(c) O(n^2)
(d) O(nlogn)

With this article at OpenGenus, the differences between Counting Sort vs Radix Sort vs Bucket Sort.