Radix Sort Algorithm in DSA Python - Build from Scratch

Radix Sort Algorithm

📖 Scenario: You work in a warehouse where you need to sort packages by their ID numbers quickly. The IDs are numbers with different digits. You want to use a method called Radix Sort to organize them from smallest to largest.

🎯 Goal: Build a program that sorts a list of package ID numbers using the Radix Sort algorithm step-by-step.

📋 What You'll Learn

Create a list of package IDs with exact values

Create a variable to track the maximum number of digits

Implement the Radix Sort logic using counting sort by digit

Print the sorted list of package IDs

💡 Why This Matters

🌍 Real World

Sorting package IDs quickly helps warehouses organize shipments efficiently.

💼 Career

Understanding Radix Sort is useful for jobs involving large-scale data sorting and optimization.

1

Create the list of package IDs

Create a list called package_ids with these exact numbers: 170, 45, 75, 90, 802, 24, 2, 66

DSA Python

# Create the list of package IDs
# Your code here

Hint

Use square brackets [] to create the list and separate numbers with commas.

2

Find the maximum number of digits

Create a variable called max_digits that stores the length of the longest number in package_ids when converted to a string

DSA Python

package_ids = [170, 45, 75, 90, 802, 24, 2, 66]
# Calculate the maximum number of digits
# Your code here

Hint

Use max() to find the largest number, then convert it to string and get its length.

3

Implement Radix Sort logic

Write a function called radix_sort that takes arr as input and sorts it using Radix Sort. Use a for loop with variable digit from 0 to max_digits - 1. Inside, implement counting sort by the current digit place.

DSA Python

package_ids = [170, 45, 75, 90, 802, 24, 2, 66]
max_digits = len(str(max(package_ids)))
# Define radix_sort function and implement sorting logic
# Your code here

Hint

Use buckets (lists) for digits 0 to 9. Extract the digit using division and modulo. Flatten buckets back to list each pass.

4

Print the sorted package IDs

Call radix_sort with package_ids and print the returned sorted list

DSA Python

package_ids = [170, 45, 75, 90, 802, 24, 2, 66]
max_digits = len(str(max(package_ids)))

def radix_sort(arr):
    for digit in range(max_digits):
        buckets = [[] for _ in range(10)]
        for number in arr:
            digit_value = (number // (10 ** digit)) % 10
            buckets[digit_value].append(number)
        arr = [num for bucket in buckets for num in bucket]
    return arr

# Print the sorted list
# Your code here

Hint

Call the function and print the result to see the sorted list.

Practice

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

easy

A. Use a pivot to partition the list and sort partitions separately

B. Compare each element with every other element and swap if needed

C. Divide the list into halves and sort each half recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing individual digits starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Other options describe Bubble Sort, Merge Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix Sort = Sort by digits from right to left [OK]

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

Common Mistakes:

• Confusing Radix Sort with comparison-based sorts
• Thinking it sorts from most significant digit first
• Assuming it uses pivot or recursion

2. Which of the following is the correct way to initialize a list of empty buckets for Radix Sort in Python?

easy

A. buckets = [[]] * 10

B. buckets = [[] for _ in range(10)]

C. buckets = [0] * 10

D. buckets = list(range(10))

Solution

1. Step 1: Understand bucket initialization

   We need 10 separate empty lists (buckets) for digits 0-9, so list comprehension creates independent lists.

2. Step 2: Analyze options

   buckets = [[]] * 10 creates 10 references to the same list, causing bugs. buckets = [0] * 10 creates integers, not lists. buckets = list(range(10)) creates a list of numbers, not buckets.

3. Final Answer:

   buckets = [[] for _ in range(10)] -> Option B

4. Quick Check:

   Independent empty lists = list comprehension [OK]

Hint: Use list comprehension for independent empty lists [OK]

Common Mistakes:

• Using [[]] * 10 causes all buckets to reference the same list
• Initializing buckets with zeros instead of lists
• Confusing range with list of empty lists

3. What will be the output of the following Python code snippet implementing one pass of Radix Sort on the least significant digit?

arr = [170, 45, 75, 90, 802, 24, 2, 66]
buckets = [[] for _ in range(10)]
for num in arr:
    digit = num % 10
    buckets[digit].append(num)
result = []
for bucket in buckets:
    result.extend(bucket)
print(result)

medium

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

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

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

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

Solution

1. Step 1: Group numbers by least significant digit

   Digits are: 170(0), 45(5), 75(5), 90(0), 802(2), 24(4), 2(2), 66(6). Buckets: 0:[170,90], 2:[802,2], 4:[24], 5:[45,75], 6:[66].

2. Step 2: Concatenate buckets in order 0 to 9

   Result list is [170, 90] + [] + [802, 2] + [] + [24] + [45, 75] + [66] + [] + [] + [] = [170, 90, 802, 2, 24, 45, 75, 66].

3. Final Answer:

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

4. Quick Check:

   Sorted by last digit = [170, 90, 802, 2, 24, 45, 75, 66] [OK]

Hint: Group by digit, then join buckets in digit order [OK]

Common Mistakes:

• Mixing digit extraction (using // instead of %)
• Not preserving order inside buckets
• Concatenating buckets in wrong order

4. The following code attempts to perform Radix Sort but has a bug. What is the error?

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        buckets = [[]] * 10
        for num in arr:
            index = (num // exp) % 10
            buckets[index].append(num)
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        exp *= 10
    return arr

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

medium

A. Using buckets = [[]] * 10 causes all buckets to reference the same list

B. The loop condition should be while max_num % exp > 0

C. The digit extraction formula is incorrect

D. The function does not return the sorted array

Solution

1. Step 1: Identify bucket initialization issue

   buckets = [[]] * 10 creates 10 references to the same list, so appending to one bucket appends to all.

2. Step 2: Check other parts

   Loop condition and digit extraction are correct. The function returns arr properly.

3. Final Answer:

   Using buckets = [[]] * 10 causes all buckets to reference the same list -> Option A

4. Quick Check:

   Bucket initialization = [[] for _ in range(10)] [OK]

Hint: Avoid [[]]*10; use list comprehension for buckets [OK]

Common Mistakes:

• Using [[]]*10 instead of list comprehension
• Changing loop condition incorrectly
• Misunderstanding digit extraction

5. You want to sort the list [329, 457, 657, 839, 436, 720, 355] using Radix Sort. After sorting by the least significant digit (units place), what will the list look like?

hard

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

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

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

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

Solution

1. Step 1: Extract least significant digit of each number

   329(9), 457(7), 657(7), 839(9), 436(6), 720(0), 355(5).

2. Step 2: Group numbers by last digit and concatenate in digit order 0-9

   Digits 0:[720], 5:[355], 6:[436], 7:[457, 657], 9:[329, 839]. Concatenate: [720, 355, 436, 457, 657, 329, 839].

3. Final Answer:

   [720, 355, 436, 457, 657, 329, 839] -> Option A

4. Quick Check:

   Sorted by units digit = [720, 355, 436, 457, 657, 329, 839] [OK]

Hint: Sort by last digit, keep order inside groups [OK]

Common Mistakes:

• Mixing digit extraction with division instead of modulo
• Not preserving order of numbers with same digit
• Concatenating buckets in wrong digit order