Skip to main content

Radix sort on 32, 45, 60, 83, ...

Short answer

Radix sort sorts by digit position from least significant to most, distributing keys into ten queues per pass and collecting in order. Each pass is stable. For the given data, after two passes the sorted list is 32, 43, 45, 60, 69, 70, 75, 83.

Explain radix sort. Sort the given data 32, 45, 60, 83, 75, 43, 70, and 69 using radix sort.

Radix sort sorts keys digit by digit from the least significant digit, distributing keys into ten queues (0 to 9) in each pass and collecting them in queue order. Each pass is stable, so after the pass for the most significant digit the list is sorted. Time is O(d·n) for d-digit keys.

Algorithm

RADIXSORT(a, n)
1. d = number of digits of the largest key
2. for pass = 1 to d
3.     put each a[i] at rear of queue[ digit pass of a[i] ]
4.     collect queue 0, 1, ..., 9 back into a

Sorting 32, 45, 60, 83, 75, 43, 70, 69 (2 passes)

Pass 1 (units digit)

Queue0123456789
Keys60, 703283, 4345, 7569

List: 60, 70, 32, 83, 43, 45, 75, 69

Pass 2 (tens digit)

Queue0-23456789
Keys3243, 4560, 6970, 7583

Answer: 32, 43, 45, 60, 69, 70, 75, 83

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →