Radix Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Radix Sort on a small array

What is the output of the following Go code that uses Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

DSA Go

package main

import (
	"fmt"
)

func countingSort(arr []int, exp int) []int {
	output := make([]int, len(arr))
	count := make([]int, 10)

	for i := 0; i < len(arr); i++ {
		index := (arr[i] / exp) % 10
		count[index]++
	}

	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	for i := len(arr) - 1; i >= 0; i-- {
		index := (arr[i] / exp) % 10
		output[count[index]-1] = arr[i]
		count[index]--
	}

	return output
}

func radixSort(arr []int) []int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}

	exp := 1
	for max/exp > 0 {
		arr = countingSort(arr, exp)
		exp *= 10
	}
	return arr
}

func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	sorted := radixSort(arr)
	fmt.Println(sorted)
}

A [2 24 45 75 66 90 170 802]

B [802 170 90 75 66 45 24 2]

C [24 2 45 66 75 90 170 802]

D [2 24 45 66 75 90 170 802]

💡 Hint

Radix sort sorts numbers digit by digit starting from the least significant digit.

Radix sort processes digits from right to left. After sorting by each digit, the array becomes more sorted. The final sorted array is [2 24 45 66 75 90 170 802].

🧠 Conceptual

intermediate

Number of passes in Radix Sort

If you apply Radix Sort to sort the array [3, 123, 45, 9, 1000], how many passes (iterations over digits) will the algorithm perform?

A 3

B 4

C 5

D 2

💡 Hint

Count the number of digits in the largest number.

The largest number is 1000 which has 4 digits, so radix sort will perform 4 passes.

🔧 Debug

advanced

Identify the error in this Radix Sort counting sort step

What error will this Go code produce when running the countingSort function inside Radix Sort?

DSA Go

func countingSort(arr []int, exp int) []int {
	output := make([]int, len(arr))
	count := make([]int, 10)

	for i := 0; i < len(arr); i++ {
		index := (arr[i] / exp) % 10
		count[index]++
	}

	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	for i := len(arr) - 1; i >= 0; i-- {
		index := (arr[i] / exp) % 10
		output[count[index]-1] = arr[i]
		count[index]--
	}

	return output
}

A runtime panic: index out of range

B compilation error: invalid for loop syntax

C incorrect sorted output

D no error, runs correctly

💡 Hint

Check the loop that updates the count array cumulative sums.

The loop for i := 1; i <= 10; i++ accesses count[10] which is out of range since count has length 10 (indices 0 to 9). This causes a runtime panic.

🚀 Application

advanced

Radix Sort on negative numbers

Given the standard Radix Sort implementation that only works with non-negative integers, what will be the output if you run it on the array [-5, 3, 0, -2, 4]?

A Runtime error due to negative indexing

B Sorted array: [-5, -2, 0, 3, 4]

C Unchanged array: [-5, 3, 0, -2, 4]

D Incorrect sorted array: [0, 3, 4, -5, -2]

💡 Hint

Radix Sort uses digits as indices; negative numbers cause issues.

Radix Sort uses digit extraction and indexing into count arrays. Negative numbers cause invalid indices leading to runtime errors.

❓ Predict Output

expert

Final array after partial Radix Sort passes

Given the array [329, 457, 657, 839, 436, 720, 355], what is the state of the array after the first pass (sorting by least significant digit) of Radix Sort?

DSA Go

package main

import (
	"fmt"
)

func countingSort(arr []int, exp int) []int {
	output := make([]int, len(arr))
	count := make([]int, 10)

	for i := 0; i < len(arr); i++ {
		index := (arr[i] / exp) % 10
		count[index]++
	}

	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	for i := len(arr) - 1; i >= 0; i-- {
		index := (arr[i] / exp) % 10
		output[count[index]-1] = arr[i]
		count[index]--
	}

	return output
}

func main() {
	arr := []int{329, 457, 657, 839, 436, 720, 355}
	arr = countingSort(arr, 1)
	fmt.Println(arr)
}

A [839 720 436 355 657 457 329]

B [329 457 657 839 436 720 355]

C [720 355 436 457 657 329 839]

D [355 436 457 329 657 839 720]

💡 Hint

Look at the last digit of each number and sort accordingly.

Sorting by least significant digit (units place): digits are [9,7,7,9,6,0,5]. Sorted order by these digits is 720(0),355(5),436(6),457(7),657(7),329(9),839(9). After stable counting sort, the array is [720 355 436 457 657 329 839].