PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q10

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Explain the basic principle of quick sort and write down its partition algorithm. Compare quick sort and merge sort. Trace the sorting steps in radix sort algorithm for the following data: 12, 11, 30, 21, 25, 39, 36, 17, 29, 10, 26, 33, 7, 9

Solution

Principle and Partition Algorithm of Quick Sort: Quick sort uses divide-and-conquer: select a pivot, partition the array so elements move left and elements move right (placing pivot in its exact final index), and recursively sort both subarrays.

Algorithm PARTITION(A, low, high):
1. pivot = A[low], i = low + 1, j = high
2. While i <= j:
       While i <= high and A[i] <= pivot: i = i + 1
       While A[j] > pivot: j = j - 1
       If i < j: swap A[i] and A[j]
3. Swap A[low] and A[j]
4. Return j

Quick Sort vs. Merge Sort:

FeatureQuick SortMerge Sort
Worst-Case Time (already sorted with bad pivot) always
Auxiliary Space stack (in-place partitioning) extra merge buffer
StabilityUnstableStable
Average Practical SpeedFaster in-RAM due to cache localitySlightly slower in-RAM; ideal for linked lists/external sort

Radix Sort Trace on 2-Digit Numbers (07, 09, ...): Input: 12, 11, 30, 21, 25, 39, 36, 17, 29, 10, 26, 33, 07, 09

  1. Units Digit ():
    • 0: 30, 10 | 1: 11, 21 | 2: 12 | 3: 33 | 5: 25 | 6: 36, 26 | 7: 17, 07 | 9: 39, 29, 09
    • Result: [30, 10, 11, 21, 12, 33, 25, 36, 26, 17, 07, 39, 29, 09]
  2. Tens Digit ():
    • 0: 07, 09
    • 1: 10, 11, 12, 17
    • 2: 21, 25, 26, 29
    • 3: 30, 33, 36, 39
    • Final Sorted List: [7, 9, 10, 11, 12, 17, 21, 25, 26, 29, 30, 33, 36, 39].
Answer:

Quick sort partitions around a pivot in-place ( average, worst), while merge sort guarantees stability using extra space. Radix sort produces: 7, 9, 10, 11, 12, 17, 21, 25, 26, 29, 30, 33, 36, 39.

All past exam questions for Data Structure and Algorithms