No Comparison: Counting Sort and Radix Sort
Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.
Introduction
This tutorial is about two awesome, non-comparison-based sorting algorithms. While many sorting algorithms require a comparator function that compares two values at a time, these two and their family of non-comparison methods rely on other techniques instead. We'll cover counting sort and radix sort, which are both very efficient. Bucket sort is another one, but it's a close enough cousin of radix sort that we'll point to other references for more information on it.
Before going into details, we must keep in mind that any sorting algorithm has to scan the unsorted array at least once. This provides us the following important rule:
Any sorting algorithm will take at least O(n) time
This statement constrains the best possible shortest sorting time - we cannot sort an array in a time complexity less than O(n). Of course, there are sorting algorithms which take up significantly more time. Given this ambitious target of O(n), let's look at how counting sort and radix sort stack up.
Here's a preview of the final implementations, but we'll be sure to walk you through the theory before revealing them again!
```py
def counting_sort(arr):
n = 0
max_num = max(arr)
counts = [0 for _ in range(max_num + 1)]
# Set up keys
for i in range(max_num + 1):
counts[i] = 0
# Count
for num in arr:
counts[num] += 1
# Order by count
for i in range(max_num + 1):
for j in range(0, counts[i]):
arr[n] = i
n += 1
return arr
def radix_sort(nums):
RADIX = 10
placement = 1
max_digit = max(nums)
while placement <= max_digit:
# declare and initialize empty buckets
buckets: list[list] = [[] for _ in range(RADIX)]
# split nums between the buckets
for i in nums:
tmp = int((i / placement) % RADIX)
buckets[tmp].append(i)
# put each buckets' contents into nums
a = 0
for bucket in range(RADIX):
for i in buckets[bucket]:
nums[a] = i
a += 1
# move to next
placement *= RADIX
return nums
print(counting_sort([5, 0, 65, 4, 10]))
print(radix_sort([5, 0, 65, 4, 10]))
```
```js
function countingSort(arr) {
let counts = [];
let n = 0;
let max = Math.max(...arr);
// Set up keys
for (let i = 0; i <= max; i++) {
counts[i] = 0;
}
// Count
for (let i = 0; i < arr.length; i++) {
counts[arr[i]]++;
}
// Order by count
for (let i = 0; i <= max; i++) {
for (let j = 0; j < counts[i]; j++) {
arr[n] = i;
n++;
}
}
return arr;
}
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function radixSort(arr) {
let maxDigits = 0;
for (let i = 0; i < arr.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(arr[i]));
}
for (let k = 0; k < maxDigits; k++) {
let buckets = Array.from({ length: 10 }, () => []);
for (let i = 0; i < arr.length; i++) {
let digit = getDigit(arr[i], k);
buckets[digit].push(arr[i]);
}
arr = [].concat(...buckets);
}
return arr;
}
console.log(radixSort([5, 0, 65, 4, 10]))
console.log(countingSort([5, 0, 65, 4, 10]));
```
```java
import java.util.*;
class Main {
static class countSort
{
static int []count;
static int [] sorted;
static int maxArray(int[] arr)
{
int max=arr[0];
for (int i=1;i<arr.length;++i)
{
if (arr[i]>max)
max = arr[i];
}
return max;
}
static int[] sort(int[]X)
{
int i;
int max = maxArray(X);
count = new int[max+1];
//initialize to zero
for (i=0;i<count.length;++i)
count[i] = 0;
//add counts to count array
for(i=0;i<X.length;++i)
{
count[X[i]] = count[X[i]] + 1;
}
//accumulate the counts
int total = count[0];
count[0] = 0;
for(i=1;i<count.length;++i)
{
int temp = total;
total = temp+count[i];
count[i] = temp;
}
sorted = new int[X.length];
//fill up the output array sorted
for( i=0;i<X.length;++i)
{
sorted[count[X[i]]] = X[i];
count[X[i]]++;
}
//put sorted in X
for( i=0;i<X.length;++i)
{
X[i] = sorted[i];
}
return X;
}
}
static class radixSort
{
static final int BASE=10;
static ArrayList<Integer>[] bucket;
static int maxArray(int[] arr)
{
int max=arr[0];
for (int i=1;i<arr.length;++i)
{
if (arr[i]>max)
max = arr[i];
}
return max;
}
static void initializeBucket()
{
bucket = new ArrayList[BASE];
for (int i=0;i<bucket.length;++i)
bucket[i] = new ArrayList<Integer>();
}
static void addXToBucket(int []X,int digit)
{
int ind;
for (int i=0;i<X.length;++i)
{
ind = (X[i]/digit)%BASE;
bucket[ind].add(X[i]);
}
}
static void addBucketToX(int []X)
{
int Xind = 0;
for (int i=0;i<bucket.length;++i)
{
for (int j=0;j<bucket[i].size();++j)
{
X[Xind] = bucket[i].get(j);
Xind++;
}
bucket[i].clear();
}
}
public static int[] sort(int [] X)
{
int max=maxArray(X);
initializeBucket();
boolean sorted = false;
int digit = 1;
while(!sorted)
{
addXToBucket(X,digit);
addBucketToX(X);
digit = digit*10;
if (max/digit==0)
sorted = true;
}
return X;
}
}
public static void main(String args[]){
int[] unsorted = {5, 0, 65, 4, 10};
System.out.print("Unsorted array: ");
System.out.println(Arrays.toString(unsorted));
System.out.print("Sorted: ");
System.out.println(Arrays.toString(countSort.sort(unsorted)));
System.out.println(Arrays.toString(radixSort.sort(unsorted)));
}
}
```CONTINUE WITH ALGODAILY PREMIUM
Keep going with the complete tutorial.
Unlock the remaining explanations and exercises, alongside the full learning library.
Explore Premium →