PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q10

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Define a radix sort with its algorithm. Trace the steps to sort the following set of data using merge sort: 85, 76, 46, 92, 30, 41 and 12.

Solution

Definition and Algorithm of Radix Sort: Radix sort is a non-comparative, stable sorting algorithm that sorts integer keys digit by digit from the Least Significant Digit (LSD) to the Most Significant Digit (MSD) using a stable distribution/counting sort at each digit position. For -digit keys in base , time complexity is .

Algorithm RADIX_SORT(A, n, d):
1. For digitPos = 0 to d - 1:
       Initialize 10 empty buckets B[0..9]
       For i = 0 to n - 1:
           digit = (A[i] / 10^digitPos) % 10
           Append A[i] to B[digit]
       Concatenate B[0], B[1], ..., B[9] back into A

Merge Sort Trace on [85, 76, 46, 92, 30, 41, 12]:

  1. Divide Phase (Recursive Splitting):
    • [85, 76, 46, 92, 30, 41, 12]
    • Left: [85, 76, 46, 92] [85, 76] and [46, 92] [85], [76], [46], [92]
    • Right: [30, 41, 12] [30, 41] and [12] [30], [41], [12]
  2. Conquer Phase (Bottom-Up Merging):
    • Merge [85] and [76] [76, 85]
    • Merge [46] and [92] [46, 92]
    • Merge [30] and [41] [30, 41]
    • Merge [76, 85] and [46, 92] [46, 76, 85, 92]
    • Merge [30, 41] and [12] [12, 30, 41]
    • Final merge of [46, 76, 85, 92] and [12, 30, 41] [12, 30, 41, 46, 76, 85, 92].
Answer:

All past exam questions for Data Structure and Algorithms