DSA SheetLesson · no judge

SORTING › RADIX SORT

Radix Sort

Reading · 7 minQuiz · 5 questions2 code drills · run onlyGenerated by gpt-5.6-luna · Aug 23

Radix sort builds a complete order one digit at a time

Least-significant-digit radix sort orders numbers by one digit place at a time, starting with the ones place. For the array [170, 45, 75, 90, 802, 24, 2, 66], each value goes into a bucket numbered 0 through 9 according to its current digit. The digit at a chosen place is extracted with (value / place) % 10, using integer division.

CPPThe expression extracts the digit at the current place.
int place = 1; // ones place
int digit = (value / place) % 10;

At place 1, the ones digits are 0, 5, 5, 0, 2, 4, 2, and 6. Put values into their buckets as you encounter them, then read the buckets from 0 through 9. Equal-digit values must leave a bucket in their arrival order, so bucket 0 contains 170 then 90, and bucket 2 contains 802 then 2.

BUCKETVALUES IN ARRIVAL ORDER
0170, 90
2802, 2
424
545, 75
666
The stable ones-place buckets

Reading those buckets produces [170, 90, 802, 2, 24, 45, 75, 66]. This row is not numerically sorted yet. It is arranged so that the ones digit is ordered, while the arrival order inside each equal-digit group is ready to carry information into the next pass.

CHECKPOINT 1Not answered

What is the exact array after the stable ones-place pass on [170, 45, 75, 90, 802, 24, 2, 66]?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

Every digit pass must preserve the order created by earlier passes

The next digit pass uses the tens digit of [170, 90, 802, 2, 24, 45, 75, 66]. The values reach their tens buckets in this order: bucket 0 gets 802 then 2, bucket 2 gets 24, bucket 4 gets 45, bucket 6 gets 66, bucket 7 gets 170 then 75, and bucket 9 gets 90.

BUCKETVALUES IN ARRIVAL ORDER
0802, 2
224
445
666
7170, 75
990
The stable tens-place buckets

Reading the tens buckets produces [802, 2, 24, 45, 66, 170, 75, 90]. Notice that 802 stays before 2 in digit-0 because they were already in that order after the ones-place pass. Likewise, 170 stays before 75 in digit-7. A pass that reverses equal-digit values can destroy the ordering established by an earlier digit, so sorting each digit is not sufficient without stability.

the stable ones-place and tens-place passes over [170, 45, 75, 90, 802, 24, 2, 66]The original array is [170, 45, 75, 90, 802, 24, 2, 66]. Sorting stably by the ones digit places 170 and 90 in bucket 0, 802 and 2 in bucket 2, 24 in bucket 4, 45 and 75 in bucket 5, and 66 in bucket 6. Reading the buckets from 0 through 9 gives [170, 90, 802, 2, 24, 45, 75, 66]. Sorting that row stably by the tens digit places 802 and 2 in bucket 0, 24 in bucket 2, 45 in bucket 4, 66 in bucket 6, 170 and 75 in bucket 7, and 90 in bucket 9. Reading those buckets gives [802, 2, 24, 45, 66, 170, 75, 90]. In every shared bucket, the first arriving number remains first.170ones=045ones=575ones=590ones=0802ones=224ones=42ones=266ones=60170→902802→2424545→75666170tens=790tens=9802tens=02tens=024tens=245tens=475tens=766tens=60802→22244456667170→7599080222445661707590onesstabletensstableORIGINALones digitONESBUCKETSarrival orderONESOUTPUTtens digitTENSBUCKETSarrival orderTENSOUTPUT
Stable buckets carry earlier digit order into the next pass.

Missing higher digits act as zero digits

The hundreds-place pass examines [802, 2, 24, 45, 66, 170, 75, 90]. Values shorter than three digits have no written hundreds digit, so their hundreds digit acts as 0. Thus 2, 24, 45, 66, 75, and 90 enter bucket 0 in their current order, while 170 enters bucket 1 and 802 enters bucket 8.

Reading the buckets gives [2, 24, 45, 66, 75, 90, 170, 802]. The maximum value is 802, which has three digit places, so the process needs the ones, tens, and hundreds passes. Stopping after the tens pass would leave 802 before the smaller values because its tens digit is 0, even though its hundreds digit is larger.

CHECKPOINT 2Not answered

Enter the array after the stable hundreds-place pass.

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The digit range controls the cost and the input rules

For this base-10 version, each digit pass scans the n values and distributes them among 10 buckets, then reads those buckets back. If d digit places are processed, the time is O(d * (n + 10)). For this trace, n is 8 and d is 3, so the work is O(3 * (8 + 10)), which is linear in the input size when the number of digit places is bounded.

The output array and the bucket storage require O(n + 10) extra space. Here that is O(8 + 10). The direct version described here accepts nonnegative integers. Signed values need an explicit extension, such as separating negative and nonnegative values and combining them in the correct order.

Next part · Quiz