Past exam question: 2066 Bhadra (Regular / Back), Q10
Open in the Padhaiko appExplain 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 jQuick Sort vs. Merge Sort:
| Feature | Quick Sort | Merge Sort |
|---|---|---|
| Worst-Case Time | (already sorted with bad pivot) | always |
| Auxiliary Space | stack (in-place partitioning) | extra merge buffer |
| Stability | Unstable | Stable |
| Average Practical Speed | Faster in-RAM due to cache locality | Slightly 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
- 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]
- Tens Digit ():
0:07, 091:10, 11, 12, 172:21, 25, 26, 293:30, 33, 36, 39- Final Sorted List:
[7, 9, 10, 11, 12, 17, 21, 25, 26, 29, 30, 33, 36, 39].
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.