Radix Sort

The idea of explained Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit.

Worst case performance - O(n.k/d)

Radix sort

 C++

void radix_sort(int array[], int length)
{
    int k = max_value(array,length);
    for (int base = 1; k/base > 0; base *= 10)
        counting_sort(array,length,base);
}

void counting_sort(int array[], int length, int base)
{
    int C[10] = {0};
    int B[length];
    for (int j = 0; j < length; j++)
        C[(array[j]/base)%10]++;
    for (int i = 1; i < 10; i++)
        C[i] = C[i] + C[i - 1];
    for (int j = length - 1; j >= 0; j--)
    {
        B[C[(array[j]/base)%10] - 1] = array[j];
        C[(array[j]/base)%10]--;
    }
    for (int i = 0; i < length; i++)
        array[i] = B[i];
}

int max_value(int array[], int length)
{
    int max = 0;
    for (int i = 0; i < length; i++)
        if (max < array[i])
            max = array[i];
    return max;
} 

Java

public int[] radix_sort(int[] array) {
    int k = max_value(array);
    for (int base = 1; k / base > 0; base *= 10) {
        array = counting_sort(array, base);
    }
    return array;
}
public int[] counting_sort(int[] array, int base) {
    int[] C = new int[10];
    int[] B = new int[array.length];
    for (int j = 0; j < array.length; j++) {
        C[(array[j]/base)%10]++;
    }
    for (int i = 1; i < 10; i++) {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = array.length - 1; j >= 0; j--) {
        B[C[(array[j]/base)%10] - 1] = array[j];
        C[(array[j]/base)%10]--;
    }
    return B;
}
public int max_value(int[] array) {
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
} 

Matlab

function array = radix_sort(array)
k = max(array);
base = 1;
while k/base > 0
    array = counting_sort(array,base);
    base = base * 10;
end

    function B = counting_sort(array,base)
        C = zeros(1,11);
        B = zeros(1,numel(array));
        for j = 1:numel(array)
            C(rem(floor(array(j)/base),10)+1) = C(rem(floor(array(j)/base),10)+1) + 1;
        end
        for i = 2:11
            C(i) = C(i) + C(i-1);
        end
        for j = numel(array):-1:1
            B(C(rem(floor(array(j)/base),10)+1)) = array(j);
            C(rem(floor(array(j)/base),10)+1) = C(rem(floor(array(j)/base),10)+1) - 1;
        end
    end
end 

Python

import math

def counting_sort(array,base):
    C = [0]* (10)
    B = [0]* (len(array))
    for j in range(len(array)):
        C[math.floor(array[j]/base)%10] = C[math.floor(array[j]/base)%10] + 1
    for i in range(1,10):
        C[i] = C[i] + C[i-1]
    for j in range(len(array)-1,-1,-1):
        B[C[math.floor(array[j]/base)%10] - 1] = array[j]
        C[math.floor(array[j]/base)%10] = C[math.floor(array[j]/base)%10] - 1
    for i in range(len(array)):
        array[i] = B[i]

def radix_sort(array):
    k = max(array)
    base = 1
    while(k/base > 0):
        counting_sort(array,base)
        base = base * 10 

Counting Sort

Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. (Introduction to Algorithms)

Worst case performance - O(n + k)

 

Counting sort

 C++

void counting_sort(int array[], int length)
{
    int k = max_value(array,length);
    int C[k+1];
    int B[length];
    memset(C, 0, sizeof(C));
    for (int j = 0; j < length; j++)
        C[array[j]]++;
    for (int i = 1; i <= k; i++)
        C[i] = C[i] + C[i - 1];
    for (int j = length - 1; j >= 0; j--)
    {
        B[C[array[j]] - 1] = array[j];
        C[array[j]]--;
    }
    print_array(B,length);
}

int max_value(int array[], int length)
{
    int max = 0;
    for (int i = 0; i < length; i++)
        if (max < array[i])
            max = array[i];
    return max;
}

void print_array(int array[], int length)
{
    for(int i=0; i<length; i++)
        cout <<array[i]<<" ";
    cout << endl;
}

 Java

public int[] counting_sort(int[] array) {
    int k = max_value(array);
    int[] C = new int[k + 1];
    int[] B = new int[array.length];
    for (int j = 0; j < array.length; j++) {
        C[array[j]]++;
    }
    for (int i = 1; i <= k; i++) {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = array.length - 1; j >= 0; j--) {
        B[C[array[j]] - 1] = array[j];
        C[array[j]]--;
    }
    return B;
}

public int max_value(int[] array) {
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

 Matlab

function B = counting_sort(array)
    k = max(array);
    C = zeros(1,k+1);
    B = zeros(1,numel(array));
    for j = 1:numel(array)
        C(array(j)) = C(array(j)) + 1;
    end
    for i = 2:k+1
        C(i) = C(i) + C(i-1);
    end
    for j = numel(array):-1:1
        B(C(array(j))) = array(j);
        C(array(j)) = C(array(j)) - 1;
    end
end

 Python

def counting_sort(array):
    k = max(array)
    C = [0]* (k+1)
    B = [0]* (len(array))
    for j in range(len(array)):
        C[array[j]] = C[array[j]] + 1
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    for j in range(len(array)-1,-1,-1):
        B[C[array[j]] - 1] = array[j]
        C[array[j]] = C[array[j]] - 1
    print(B)