Radix Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

Start with least significant digit

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets

↓

Move to next more significant digit

↓

Repeat until all digits processed

↓

Sorted array

Radix Sort processes numbers digit by digit from least to most significant, grouping by digit and collecting until fully sorted.

Execution Sample

DSA C#

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
RadixSort(arr);
// Sorts array by digits from least to most significant

Sorts the array by grouping numbers by each digit starting from the rightmost digit.

Execution Table

Step	Operation	Digit Place	Buckets (0-9)	Array After Collection	Visual State
1	Find max number	-	-	-	[170, 45, 75, 90, 802, 24, 2, 66]
2	Sort by least significant digit (1s place)	1	0:[170, 90], 2:[802, 2], 4:[24], 5:[45, 75], 6:[66], others:[]	[170, 90, 802, 2, 24, 45, 75, 66]	[170, 90, 802, 2, 24, 45, 75, 66]
3	Sort by next digit (10s place)	10	0:[802, 2], 2:[24], 4:[45], 6:[66], 7:[170, 75], 9:[90], others:[]	[802, 2, 24, 45, 66, 170, 75, 90]	[802, 2, 24, 45, 66, 170, 75, 90]
4	Sort by next digit (100s place)	100	0:[2, 24, 45, 66, 75, 90], 1:[170], 8:[802], others:[]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
5	All digits processed, array sorted	-	-	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]

💡 All digit places processed up to max number's digit count, sorting complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[170, 45, 75, 90, 802, 24, 2, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	[802, 2, 24, 45, 66, 170, 75, 90]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
digitPlace	N/A	1	10	100	N/A
maxNumber	802	802	802	802	802

Key Moments - 3 Insights

Why do we start sorting from the least significant digit (rightmost) instead of the most significant digit?

Starting from the least significant digit ensures that sorting by higher digits preserves the order of lower digits, maintaining stability as shown in steps 2 to 4 in the execution_table.

How do buckets help in sorting the numbers by each digit?

Buckets group numbers sharing the same digit at the current place, making it easy to collect them in order, as seen in the 'Buckets' column in steps 2 to 4.

What happens if numbers have different digit lengths?

Shorter numbers are treated as having 0 in higher digit places, so they go into bucket 0, ensuring correct order, as seen with numbers like 2 and 24 in steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the array state after collecting from buckets?

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

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

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

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

💡 Hint

Check the 'Array After Collection' column in Step 3 of the execution_table.

At which step does the sorting by the 100s digit place occur?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Digit Place' column in the execution_table.

If the max number was 99 instead of 802, how many digit places would the algorithm process?

A 3

B 1

C 2

D 4

💡 Hint

The number of digit places equals the number of digits in the max number, check 'maxNumber' in variable_tracker.

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant.
- Uses buckets (0-9) to group numbers by current digit.
- Collects numbers from buckets after each digit pass.
- Repeats until all digit places of max number processed.
- Stable and efficient for fixed digit-length numbers.

Full Transcript

Radix Sort works by sorting numbers starting from the least significant digit (rightmost) to the most significant digit (leftmost). First, it finds the maximum number to know how many digits to process. Then, for each digit place, it places numbers into buckets based on the digit at that place. After placing, it collects numbers from buckets back into the array. This process repeats for each digit place until all digits are processed. The array becomes sorted at the end. Buckets help group numbers by digit, and starting from the least significant digit keeps the sorting stable. Shorter numbers are treated as having zeros in higher digit places, ensuring correct order. This method is efficient for sorting numbers with fixed digit lengths.

Practice

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

easy

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

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers by swapping adjacent elements repeatedly

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort uses digit positions to sort without direct comparisons between whole numbers.

3. Final Answer:

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

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

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

Common Mistakes:

• Thinking Radix Sort compares whole numbers directly
• Confusing Radix Sort with quicksort or mergesort
• Assuming it sorts from most significant digit first

2. Which of the following is the correct way to initialize a queue in C# for use in Radix Sort?

easy

A. Queue<int> buckets = new Queue<int>[10];

B. Queue<int> buckets = new Queue<int>(10);

C. Queue buckets = new Queue<int>(10);

D. Queue<int>[] buckets = new Queue<int>[10];

Solution

1. Step 1: Understand array of queues declaration

   We need an array of 10 queues, so the correct syntax is an array of Queue<int>: Queue<int>[] buckets = new Queue<int>[10];

2. Step 2: Check other options

   Queue<int> buckets = new Queue<int>[10]; tries to assign an array to a single Queue<int> variable, which is invalid. Queue buckets = new Queue<int>(10); uses non-generic Queue incorrectly. Queue<int> buckets = new Queue<int>(10); creates a single Queue with capacity 10, not an array.

3. Final Answer:

   Queue<int>[] buckets = new Queue<int>[10]; -> Option D

4. Quick Check:

   Array of queues = Queue<int>[] [OK]

Hint: Use [] to declare array of queues in C# [OK]

Common Mistakes:

• Declaring a single queue instead of an array
• Using non-generic Queue instead of Queue<int>
• Confusing array initialization syntax

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

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
RadixSort(arr);
Console.WriteLine(string.Join(", ", arr));

medium

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

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

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

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

Solution

1. Step 1: Apply Radix Sort on given array

   Radix Sort sorts numbers by digits from least significant to most significant. After sorting, the array becomes sorted in ascending order: 2, 24, 45, 66, 75, 90, 170, 802.

2. Step 2: Verify output matches sorted array

   [2, 24, 45, 66, 75, 90, 170, 802] matches the sorted array. [170, 45, 75, 90, 802, 24, 2, 66] is original unsorted. [802, 170, 90, 75, 66, 45, 24, 2] is descending order. [24, 2, 45, 66, 75, 90, 170, 802] is incorrect order.

3. Final Answer:

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

4. Quick Check:

   Radix Sort output = Sorted array ascending [OK]

Hint: Radix Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing original and sorted array
• Assuming Radix Sort sorts descending
• Mixing digit order in sorting

4. Identify the error in this Radix Sort code snippet in C#:

for (int i = 0; i < maxDigit; i++)
{
    Queue<int>[] buckets = new Queue<int>[10];
    for (int j = 0; j < 10; j++)
        buckets[j] = new Queue<int>();

    foreach (int num in arr)
    {
        int digit = (num / (int)Math.Pow(10, i)) % 10;
        buckets[digit].Enqueue(num);
    }

    int index = 0;
    foreach (var bucket in buckets)
    {
        while (bucket.Count > 0)
            arr[index++] = bucket.Dequeue();
    }
}

medium

A. The inner foreach loop should use a for loop instead

B. The digit calculation is incorrect; it should use modulus 100

C. There is no error in the code snippet

D. The buckets array is reinitialized inside the outer loop, causing loss of data

Solution

1. Step 1: Analyze the code structure

   The code correctly creates fresh buckets for each digit position, distributes all elements by the current digit using stable queues, and reconstructs the array in place. This is proper LSD Radix Sort implementation.

2. Step 2: Evaluate options

   A: foreach loops are fine for iterating arr and buckets. B: (num / pow(10,i)) % 10 correctly extracts the i-th digit from LSD. C: Reinitializing buckets each pass prevents carry-over from previous passes and does not lose data since all elements are re-enqueued from arr every iteration.

3. Final Answer:

   There is no error in the code snippet -> Option C

4. Quick Check:

   Buckets reinitialized each pass = Correct [OK]

Hint: Buckets reset each digit pass is required, not an error [OK]

Common Mistakes:

• Thinking buckets reinitialization causes data loss
• Misunderstanding digit extraction formula
• Resetting index inside wrong loop

5. You want to adapt Radix Sort to sort an array of strings representing numbers with varying lengths (e.g., ["170", "45", "9", "802", "24"]). Which approach is best to handle different string lengths correctly?

hard

A. Pad shorter strings with leading zeros to match the longest length before sorting

B. Sort strings as they are without padding, digit by digit from left to right

C. Convert strings to integers and apply normal Radix Sort

D. Sort strings by length first, then apply Radix Sort on digits

Solution

1. Step 1: Understand problem with varying string lengths

   Radix Sort requires uniform digit positions. Strings of different lengths cause misalignment when sorting digit by digit.

2. Step 2: Choose padding strategy

   Padding shorter strings with leading zeros makes all strings equal length, allowing digit-by-digit sorting from right to left correctly.

3. Step 3: Evaluate other options

   Sort strings as they are without padding, digit by digit from left to right sorts left to right which breaks Radix Sort logic. Convert strings to integers and apply normal Radix Sort loses string format and may cause overflow. Sort strings by length first, then apply Radix Sort on digits sorting by length first does not solve digit alignment.

4. Final Answer:

   Pad shorter strings with leading zeros to match the longest length before sorting -> Option A

5. Quick Check:

   Pad strings to equal length = Correct approach [OK]

Hint: Pad strings with zeros to equal length before sorting [OK]

Common Mistakes:

• Sorting strings without padding causes wrong order
• Sorting digits left to right breaks Radix Sort
• Converting strings to int may cause errors with large numbers