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].

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers by dividing the list into halves recursively

B. Sort numbers by processing individual digits from least to most significant

C. Sort numbers by comparing each pair directly

D. Sort numbers by swapping adjacent elements repeatedly

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by grouping digits and sorting them digit by digit, starting from the least significant digit.

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts (like bubble or merge sort), Radix Sort processes digits individually without direct element comparisons.

3. Final Answer:

   Sort numbers by processing individual digits from least to most significant -> Option B

4. Quick Check:

   Radix Sort = Digit-wise sorting [OK]

Hint: Radix Sort sorts digits from right to left [OK]

Common Mistakes:

• Thinking Radix Sort compares elements directly
• Confusing Radix Sort with divide and conquer methods
• Assuming it swaps adjacent elements like bubble sort

2. Which of the following is the correct way to initialize a slice of buckets for Radix Sort in Go?

easy

A. buckets := [][]int{}

B. buckets := make([]int, 10)

C. buckets := make([][]int, 10)

D. buckets := [10]int{}

Solution

1. Step 1: Identify bucket type needed

   Radix Sort uses buckets to hold multiple integers per digit, so each bucket must be a slice of ints.

2. Step 2: Choose correct slice initialization

   Using make([][]int, 10) creates a slice of 10 slices, perfect for buckets 0-9.

3. Final Answer:

   buckets := make([][]int, 10) -> Option C

4. Quick Check:

   Slice of slices for buckets = buckets := make([][]int, 10) [OK]

Hint: Buckets hold slices, so use [][]int with make [OK]

Common Mistakes:

• Using single int slice instead of slice of slices
• Using array instead of slice for dynamic buckets
• Initializing empty slice without length

3. What will be the output of the following Go code snippet using Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

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

func radixSort(arr []int) {
  max := getMax(arr)
  exp := 1
  for max/exp > 0 {
    countSort(arr, exp)
    exp *= 10
  }
}

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

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

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

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

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

  for i := 0; i < n; i++ {
    arr[i] = output[i]
  }
}

medium

A. [2 24 45 66 75 90 802 170]

B. [802 170 90 75 66 45 24 2]

C. [170 45 75 90 802 24 2 66]

D. [2 24 45 66 75 90 170 802]

Solution

1. Step 1: Understand Radix Sort process on given array

   Radix Sort sorts by digits from least significant to most significant. After sorting by units, tens, and hundreds place, the array becomes sorted.

2. Step 2: Trace final sorted array

   The final sorted array is ascending: [2, 24, 45, 66, 75, 90, 170, 802].

3. Final Answer:

   [2 24 45 66 75 90 170 802] -> Option D

4. Quick Check:

   Radix Sort output = Sorted ascending array [OK]

Hint: Radix Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing order of digits processed
• Misreading output as original array
• Mixing up output with descending order

4. Identify the bug in this Radix Sort countSort function snippet in Go:

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

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

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

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

  for i := 0; i < n; i++ {
    arr[i] = output[i]
  }
}

medium

A. The last for loop should iterate backwards from n-1 to 0

B. The count array size should be 100 instead of 10

C. The output slice should be initialized with zeros explicitly

D. The index calculation should use modulo 100 instead of 10

Solution

1. Step 1: Check order of placing elements in output

   To maintain stable sorting, elements must be placed from right to left (backwards) in output.

2. Step 2: Identify incorrect loop direction

   The code uses a forward loop (0 to n-1) which breaks stability; it should loop from n-1 down to 0.

3. Final Answer:

   The last for loop should iterate backwards from n-1 to 0 -> Option A

4. Quick Check:

   Stable sort needs backward loop [OK]

Hint: Place elements backward to keep stable order [OK]

Common Mistakes:

• Looping forward breaks stability
• Changing count array size unnecessarily
• Misunderstanding index calculation

5. You want to sort a list of strings representing numbers with varying lengths using Radix Sort in Go. Which approach correctly adapts Radix Sort for this case?

hard

A. Pad all strings with leading zeros to equal length, then sort digit by digit from right to left

B. Sort strings by length first, then apply Radix Sort on digits from left to right

C. Convert strings to integers and apply normal Radix Sort directly

D. Use Radix Sort only on the first character of each string

Solution

1. Step 1: Handle varying string lengths

   Pad strings with leading zeros so all have equal length, ensuring digit positions align.

2. Step 2: Apply Radix Sort digit by digit from right to left

   After padding, sort from least significant digit (rightmost) to most significant (leftmost) to maintain correct order.

3. Final Answer:

   Pad all strings with leading zeros to equal length, then sort digit by digit from right to left -> Option A

4. Quick Check:

   Padding equalizes length for Radix Sort [OK]

Hint: Pad strings to same length before sorting digits [OK]

Common Mistakes:

• Sorting by length first breaks digit alignment
• Converting strings to int may overflow or lose leading zeros
• Sorting only first character ignores full number