Past exam question: 2078 Baishakh (Back), Q8
Open in the Padhaiko appQuestion
Define stability and efficiency of sorting algorithms. Sort 14, 2, 205, 918, 231, 4, 44, 1110, 666 and 840 radix sort.
Solution
Stability and Efficiency of Sorting Algorithms:
- Stability: A sorting algorithm is stable if elements with equal keys preserve their original relative order in the sorted output (important when sorting multi-field records by secondary then primary keys). Examples: Insertion, Merge, Bubble, and Radix sort (with counting sort per digit).
- Efficiency: Measured by time complexity (comparisons/swaps as a function of , e.g., vs. ) and space complexity (in-place vs. extra buffer).
Radix Sort Setup (4-Digit Zero-Padded Representation): Max value is 1110 ( digits). Pad all numbers to 4 digits: 0014, 0002, 0205, 0918, 0231, 0004, 0044, 1110, 0666, 0840
Digit-by-Digit Counting/Bucket Passes (LSD to MSD):
- Units Digit ():
0:1110, 08401:02312:00024:0014, 0004, 00445:02056:06668:0918- List:
[1110, 0840, 0231, 0002, 0014, 0004, 0044, 0205, 0666, 0918]
- Tens Digit ():
0:0002, 0004, 02051:1110, 0014, 09183:02314:0840, 00446:0666- List:
[0002, 0004, 0205, 1110, 0014, 0918, 0231, 0840, 0044, 0666]
- Hundreds Digit ():
0:0002, 0004, 0014, 00441:11102:0205, 02316:06668:08409:0918- List:
[0002, 0004, 0014, 0044, 1110, 0205, 0231, 0666, 0840, 0918]
- Thousands Digit ():
0:0002, 0004, 0014, 0044, 0205, 0231, 0666, 0840, 09181:1110- List:
[2, 4, 14, 44, 205, 231, 666, 840, 918, 1110]
Answer:
- Stability preserves relative order of equal keys; efficiency quantifies asymptotic time and extra space.
- Radix Sort Result:
2, 4, 14, 44, 205, 231, 666, 840, 918, 1110.