Radix Sort Algorithm in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Radix Sort?

Radix Sort is a sorting method that sorts numbers digit by digit, starting from the least significant digit to the most significant digit.

intermediate

How does Radix Sort handle sorting of numbers with different digit lengths?

Radix Sort treats shorter numbers as if they have leading zeros, so all numbers are compared digit by digit at the same positions.

intermediate

What is the main helper technique used inside Radix Sort to sort digits at each step?

Radix Sort uses a stable sorting method like Counting Sort to sort numbers based on the current digit without changing the order of equal elements.

advanced

Why is Radix Sort efficient for sorting large lists of numbers with fixed digit length?

Because it sorts digits individually and uses Counting Sort which runs in linear time, Radix Sort can sort large lists faster than comparison-based sorts when digit length is fixed.

advanced

What is the time complexity of Radix Sort?

The time complexity is O(d * (n + k)) where d is the number of digits, n is the number of elements, and k is the range of digit values (usually 10).

Which digit does Radix Sort start sorting from?

A Least significant digit (rightmost)

B Most significant digit (leftmost)

C Middle digit

D Random digit

Radix Sort starts sorting from the least significant digit to ensure correct order after all passes.

What kind of sorting algorithm is used inside Radix Sort for sorting digits?

A Stable sorting algorithm

B Unstable sorting algorithm

C Recursive sorting algorithm

D Divide and conquer sorting algorithm

Radix Sort uses a stable sorting algorithm like Counting Sort to keep the relative order of equal elements.

What is the main advantage of Radix Sort over comparison-based sorts?

A It sorts strings faster

B It uses less memory

C It can sort in linear time for fixed digit length

D It works only on sorted data

Radix Sort can sort numbers in linear time when digit length is fixed, unlike comparison sorts which are at best O(n log n).

If you have numbers with different digit lengths, how does Radix Sort treat them?

A Sorts by number length first

B Ignores shorter numbers

C Sorts only the longest numbers

D Pads shorter numbers with leading zeros

Radix Sort treats shorter numbers as if they have leading zeros to align digits for sorting.

What is the range of digit values (k) usually used in Radix Sort?

A 26 (letters in alphabet)

B 10 (digits 0 to 9)

C 2 (binary digits)

D 100 (percent values)

Radix Sort usually sorts decimal digits, so k is 10 for digits 0 through 9.

Explain how Radix Sort works step-by-step on a list of numbers.

Think about sorting digits one by one from right to left.

Describe why Radix Sort requires a stable sorting algorithm internally.

Consider what happens if order changes between digit sorts.

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