×

Search anything:

# Counting Sort vs Radix Sort vs Bucket Sort

#### Algorithms Sorting Algorithms

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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 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++){
}
for(int i=0; i < n; i++){
int bucketI =(k * arr[i]/max_val;
}
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.

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

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

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