Data Structure Radix Sort Practice Questions with Solutions

By /

Introduction

Radix Sort is a non-comparison sorting algorithm that sorts numbers digit by digit. Instead of comparing complete numbers, it processes digits from the least significant digit to the most significant digit. Counting Sort is commonly used internally to arrange numbers at each digit position. In this chapter, you will practice Radix Sort with JavaScript through 10 solved questions covering digit extraction, multiple passes, ascending and descending sorting, duplicate numbers, negative numbers, and reusable functions. Data Structure Radix Sort practice questions with solutions help to understand the concepts.

Question 1: Sort Numbers Using Radix Sort

Question

Sort the following array in ascending order using Radix Sort:

let numbers = [170, 45, 75, 90, 802, 24, 2, 66];

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        let digit = getDigit(number, position);
        count[digit]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    let max = Math.max(...arr);

    for (let position = 0; Math.pow(10, Math.floor(Math.log10(max))); position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [170, 45, 75, 90, 802, 24, 2, 66];

console.log(radixSort(numbers));

Output

[2, 24, 45, 66, 75, 90, 170, 802]

Radix Sort processes the numbers from the ones digit, then the tens digit, and finally the hundreds digit.

Question 2: Extract a Specific Digit

Question

Write a JavaScript function that extracts a digit from a number based on its position.

For:

let number = 583;

Find:

  • Ones digit
  • Tens digit
  • Hundreds digit

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

let number = 583;

console.log("Ones:", getDigit(number, 0));
console.log("Tens:", getDigit(number, 1));
console.log("Hundreds:", getDigit(number, 2));

Output

Ones: 3
Tens: 8
Hundreds: 5

In Radix Sort, digit positions normally start from 0:

position 0 → Ones
position 1 → Tens
position 2 → Hundreds

Question 3: Understand Radix Sort Passes

Question

For the following array:

let numbers = [329, 457, 657, 839, 436, 720, 355];

Show the array after each major digit pass of Radix Sort.

Solution

First, sort according to the ones digit:

[720, 355, 436, 457, 657, 329, 839]

Next, sort according to the tens digit:

[720, 329, 436, 839, 355, 457, 657]

Finally, sort according to the hundreds digit:

[329, 355, 436, 457, 657, 720, 839]

Output

After ones digit:
[720, 355, 436, 457, 657, 329, 839]

After tens digit:
[720, 329, 436, 839, 355, 457, 657]

After hundreds digit:
[329, 355, 436, 457, 657, 720, 839]

The important point is that Radix Sort does not try to completely sort the array in the first pass. Each pass organizes the array according to one digit position.

Question 4: Sort Numbers with Different Number of Digits

Question

Use Radix Sort to sort:

let numbers = [5, 21, 3, 45, 12, 100, 8];

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        count[getDigit(number, position)]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    let max = Math.max(...arr);
    let digits = max === 0 ? 1 : Math.floor(Math.log10(max)) + 1;

    for (let position = 0; position < digits; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [5, 21, 3, 45, 12, 100, 8];

console.log(radixSort(numbers));

Output

[3, 5, 8, 12, 21, 45, 100]

Numbers with fewer digits are treated as if they have leading zeroes.

For example:

5   → 005
21  → 021
100 → 100

Question 5: Count the Number of Digit Passes

Question

Find how many digit passes Radix Sort needs for:

let numbers = [12, 45, 789, 34, 5, 1234];

Solution

The largest number is:

1234

It contains four digits.

Therefore Radix Sort needs four passes:

1. Ones
2. Tens
3. Hundreds
4. Thousands

We can calculate it using JavaScript:

let numbers = [12, 45, 789, 34, 5, 1234];

let max = Math.max(...numbers);

let passes = max === 0
    ? 1
    : Math.floor(Math.log10(max)) + 1;

console.log("Digit passes:", passes);

Output

Digit passes: 4

The number of passes depends on the number of digits in the largest value.

Question 6: Sort Numbers with Duplicate Values

Question

Sort the following array using Radix Sort while keeping all duplicate values:

let numbers = [121, 432, 121, 56, 432, 78];

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        count[getDigit(number, position)]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    let max = Math.max(...arr);
    let digits = max === 0 ? 1 : Math.floor(Math.log10(max)) + 1;

    for (let position = 0; position < digits; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [121, 432, 121, 56, 432, 78];

console.log(radixSort(numbers));

Output

[56, 78, 121, 121, 432, 432]

The duplicate values 121 and 432 are preserved.

Question 7: Sort an Array of Three-Digit Numbers

Question

Sort the following three-digit numbers using Radix Sort:

let numbers = [305, 102, 999, 410, 208, 150];

Solution

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        let digit = Math.floor(number / Math.pow(10, position)) % 10;
        count[digit]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = Math.floor(arr[i] / Math.pow(10, position)) % 10;

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    for (let position = 0; position < 3; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [305, 102, 999, 410, 208, 150];

console.log(radixSort(numbers));

Output

[102, 150, 208, 305, 410, 999]

Because every value contains three digits, exactly three digit passes are required.

Question 8: Sort Large Integer Values

Question

Use Radix Sort to arrange these numbers:

let numbers = [1050, 25, 300, 7, 9999, 120];

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        count[getDigit(number, position)]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    let max = Math.max(...arr);

    let digits = max === 0
        ? 1
        : Math.floor(Math.log10(max)) + 1;

    for (let position = 0; position < digits; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [1050, 25, 300, 7, 9999, 120];

console.log(radixSort(numbers));

Output

[7, 25, 120, 300, 1050, 9999]

The algorithm automatically determines that four digit positions are needed because 9999 is the largest value.

Question 9: Sort Numbers in Descending Order

Question

Modify Radix Sort to produce the numbers in descending order:

let numbers = [170, 45, 75, 90, 24, 66];

Solution

One simple approach is to first perform normal Radix Sort and then reverse the resulting array.

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        count[getDigit(number, position)]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    let max = Math.max(...arr);
    let digits = max === 0 ? 1 : Math.floor(Math.log10(max)) + 1;

    for (let position = 0; position < digits; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers = [170, 45, 75, 90, 24, 66];

let sorted = radixSort(numbers);

console.log(sorted.reverse());

Output

[170, 90, 75, 66, 45, 24]

This approach first creates an ascending result and then reverses it.

Question 10: Create a Reusable Radix Sort Function

Question

Create a reusable Radix Sort function and test it with two different arrays:

[91, 45, 12, 305, 67]

and

[500, 21, 9, 87, 120]

Solution

function getDigit(number, position) {
    return Math.floor(number / Math.pow(10, position)) % 10;
}

function countingSortByDigit(arr, position) {
    let output = new Array(arr.length);
    let count = new Array(10).fill(0);

    for (let number of arr) {
        count[getDigit(number, position)]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        let digit = getDigit(arr[i], position);

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    return output;
}

function radixSort(arr) {
    if (arr.length === 0) {
        return [];
    }

    let max = Math.max(...arr);

    let digits = max === 0
        ? 1
        : Math.floor(Math.log10(max)) + 1;

    for (let position = 0; position < digits; position++) {
        arr = countingSortByDigit(arr, position);
    }

    return arr;
}

let numbers1 = [91, 45, 12, 305, 67];
let numbers2 = [500, 21, 9, 87, 120];

console.log(radixSort(numbers1));
console.log(radixSort(numbers2));

Output

[12, 45, 67, 91, 305]
[9, 21, 87, 120, 500]

The same Radix Sort function can now be reused for different arrays of non-negative integers.

Key Takeaways

  • Radix Sort is a non-comparison sorting algorithm.
  • It sorts numbers digit by digit.
  • The usual process starts with the least significant digit.
  • It then moves toward the most significant digit.
  • Counting Sort is commonly used for sorting each digit position.
  • Numbers with fewer digits are handled using implicit leading zeroes.
  • Duplicate values are preserved.
  • The number of digit passes depends on the number of digits in the largest value.
  • Radix Sort is particularly useful for integers with a manageable number of digits.
  • For n numbers and d digit positions, a common implementation has time complexity around O(d × (n + k)), where k is the digit base, commonly 10.
  • With decimal digits, k = 10, so the complexity is often simplified to O(d × n).
  • Standard Radix Sort implementations using extra arrays require additional memory.
  • Basic Radix Sort implementations like the ones in this chapter are designed for non-negative integers.

FAQs

1. What is Radix Sort in Data Structures?

Radix Sort is a sorting algorithm that organizes numbers by processing their individual digits instead of directly comparing complete values.

2. Is Radix Sort a comparison-based sorting algorithm?

No. Radix Sort is a non-comparison-based sorting algorithm.

3. Which digit does Radix Sort process first?

The common LSD Radix Sort approach starts with the least significant digit, which is the ones digit.

4. What sorting algorithm is commonly used inside Radix Sort?

Counting Sort is commonly used to sort the elements according to each individual digit.

5. What is the time complexity of Radix Sort?

For n elements, d digit positions, and digit range k, the typical complexity is O(d × (n + k)).

6. Can Radix Sort handle duplicate numbers?

Yes. Radix Sort can sort duplicate values while preserving every occurrence.

7. Can basic Radix Sort handle negative numbers?

The basic implementation used in this chapter is intended for non-negative integers. Negative numbers require additional handling, such as separating negative and non-negative values before sorting.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top