#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/radix-sort-code

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/radix-sort-code

Repovive

Radix Sort - Code - Sorting Algorithms | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Radix Sort - Code

Implementation and analysis.

Here is the implementation of radix sort:

function radixSort(arr):
    maxVal = max(arr)
    exp = 1
    while maxVal / exp >= 1:
        countingSortByDigit(arr, exp)
        exp = exp * 10

function countingSortByDigit(arr, exp):
    n = arr.length
    output = array of size n
    count = array of size 10, all zeros

    for i from 0 to n-1:
        digit = (arr[i] / exp) mod 10
        count[digit] = count[digit] + 1

    for i from 1 to 9:
        count[i] = count[i] + count[i-1]

    for i from n-1 down to 0:
        digit = (arr[i] / exp) mod 10
        output[count[digit] - 1] = arr[i]
        count[digit] = count[digit] - 1

    copy output to arr

Time: $O(d \cdot (n + k))$ where $d$ is the number of digits and $k$ is the base (10 for decimal).

Space: $O(n + k)$ (excluding input array).