PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

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:

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):

  1. Units Digit ():
    • 0: 1110, 0840
    • 1: 0231
    • 2: 0002
    • 4: 0014, 0004, 0044
    • 5: 0205
    • 6: 0666
    • 8: 0918
    • List: [1110, 0840, 0231, 0002, 0014, 0004, 0044, 0205, 0666, 0918]
  2. Tens Digit ():
    • 0: 0002, 0004, 0205
    • 1: 1110, 0014, 0918
    • 3: 0231
    • 4: 0840, 0044
    • 6: 0666
    • List: [0002, 0004, 0205, 1110, 0014, 0918, 0231, 0840, 0044, 0666]
  3. Hundreds Digit ():
    • 0: 0002, 0004, 0014, 0044
    • 1: 1110
    • 2: 0205, 0231
    • 6: 0666
    • 8: 0840
    • 9: 0918
    • List: [0002, 0004, 0014, 0044, 1110, 0205, 0231, 0666, 0840, 0918]
  4. Thousands Digit ():
    • 0: 0002, 0004, 0014, 0044, 0205, 0231, 0666, 0840, 0918
    • 1: 1110
    • List: [2, 4, 14, 44, 205, 231, 666, 840, 918, 1110]
Answer:

All past exam questions for Data Structure and Algorithms