Past exam question: 2063 Baishakh (Regular / Back), Q8
Open in the Padhaiko appQuestion
Explain the basic principle of radix sort. Trace the sorting steps in quick sort and radix sort. 25,57,48,37,12,92,86,33
Solution
Basic Principle of Radix Sort: Radix sort sorts keys without element-to-element comparisons by grouping them stably digit-by-digit into buckets (0..9) starting from the Least Significant Digit (LSD) up to the Most Significant Digit (MSD).
1. Quick Sort Trace on [25, 57, 48, 37, 12, 92, 86, 33] (First-Element Pivot):
- Pivot
25:istops at57,jstops at12(idx 4). Swap57&12[25, 12, 48, 37, 57, 92, 86, 33]. Nextj=1(12), swap25&12:[12] [25] [48, 37, 57, 92, 86, 33]. - Right
[48, 37, 57, 92, 86, 33], Pivot48: swap57&33[48, 37, 33, 92, 86, 57]; swap48&33:[33, 37] [48] [92, 86, 57]. - Subarray
[33, 37], Pivot33: stays[33, 37]. - Subarray
[92, 86, 57], Pivot92: swap92&57[57, 86] [92]; pivot57stays[57, 86]. - Sorted:
[12, 25, 33, 37, 48, 57, 86, 92].
2. Radix Sort Trace on [25, 57, 48, 37, 12, 92, 86, 33]:
- Pass 1 (Units Digit):
2:12, 92|3:33|5:25|6:86|7:57, 37|8:48- List:
[12, 92, 33, 25, 86, 57, 37, 48]
- Pass 2 (Tens Digit):
1:12|2:25|3:33, 37|4:48|5:57|8:86|9:92- Sorted:
[12, 25, 33, 37, 48, 57, 86, 92].
Answer:
Both quick sort and radix sort produce the sorted sequence: 12, 25, 33, 37, 48, 57, 86, 92.