- 2069 Poush · 5 marks
Radix sort on 25, 57, 48, 37, ...
Short answer
Radix sort: two passes, distributing by units then tens into ten queues. Final sorted list: 12, 25, 33, 37, 48, 57, 86, 92.
Trace the sorting steps in radix sort for: 25, 57, 48, 37, 12, 92, 86, 33 showing status of all queues in each iterations.
Radix sort uses 10 queues; the maximum key is 92 (2 digits), so 2 passes are needed.
Initial list: 25, 57, 48, 37, 12, 92, 86, 33
Pass 1 (units digit)
| Queue | Contents (front to rear) |
|---|---|
| 0 | empty |
| 1 | empty |
| 2 | 12, 92 |
| 3 | 33 |
| 4 | empty |
| 5 | 25 |
| 6 | 86 |
| 7 | 57, 37 |
| 8 | 48 |
| 9 | empty |
After collecting: 12, 92, 33, 25, 86, 57, 37, 48
Pass 2 (tens digit)
| Queue | Contents (front to rear) |
|---|---|
| 0 | empty |
| 1 | 12 |
| 2 | 25 |
| 3 | 33, 37 |
| 4 | 48 |
| 5 | 57 |
| 6, 7 | empty |
| 8 | 86 |
| 9 | 92 |
After collecting: 12, 25, 33, 37, 48, 57, 86, 92
Answer: 12, 25, 33, 37, 48, 57, 86, 92
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Heap sort on 37, 33, 26, 92, ... · Data Structure and Algorithm, chapter 7
- Merge and radix sort on 142, 523, ... · Data Structure and Algorithm, chapter 7
- Merge sort on 85, 76, 46, 92, ... · Data Structure and Algorithm, chapter 7
- Straight selection sort on 33, 90, 45, ... · Data Structure and Algorithm, chapter 7
- Radix sort on 345, 654, 924, ... · Data Structure and Algorithm, chapter 7
- Shell sort on 92, 83, 22, 49, ... · Data Structure and Algorithm, chapter 7