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)