Radix Sort

best video:

pseudocode:

Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        for i = 0 to n do
         count[key of(A[i]) in pass j]++
 
        for k = 1 to 10 do
         count[k] = count[k] + count[k-1]
 
        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--
 
        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]
 
    end for(j)
end func

implementation: (I need to clear the radix sort part later..took help to implement)

// C implementation of Radix Sort
#include<bits/stdc++.h>

// This  function gives maximum value in array[]
int getMax(int A[], int n)
{
    int i;
    int max = A[0];
    for (i = 1; i < n; i++){
        if (A[i] > max)
            max = A[i];
    }
    return max;
}

// Main Radix Sort sort function
void radixSort(int A[], int n)
{
    int i,digitPlace = 1;
    int result[n]; // resulting array
    // Find the largest number to know number of digits
    int largestNum = getMax(A, n);


    //we run loop until we reach the largest digit place
    while(largestNum/digitPlace >0){

        int count[10] = {0};
         //Store the count of "keys" or digits in count[]
        for (i = 0; i < n; i++)
            count[ (A[i]/digitPlace)%10 ]++;

        // Change count[i] so that count[i] now contains actual
        //  position of this digit in result[]
        //  Working similar to the counting sort algorithm
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the resulting array
        for (i = n - 1; i >= 0; i--)
        {
            result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
            count[ (A[i]/digitPlace)%10 ]--;
        }

        // Now main array A[] contains sorted
        // numbers according to current digit place
        for (i = 0; i < n; i++)
            A[i] = result[i];

            // Move to next digit place
            digitPlace *= 10;
    }
}

// Function to print an array
void printArray(int A[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    printf("%d ", A[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int a[] = {432,312,304,310,123,124};
    int n = sizeof(a)/sizeof(a[0]);
    printf("Unsorted Array: ");
    printArray(a, n);

    radixSort(a, n);

    printf("Sorted Array: ");
    printArray(a, n);
    return 0;
}

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number