Past exam question: 2066 Jestha (Back), Q7
Open in the Padhaiko appQuestion
Define internal and external sorting. Write an algorithm for quick sort and trace your algorithm for a given sequence of data. 5, 43, 99, 20, 45, 7, 6, 63, 92, 4.
Solution
Internal vs. External Sorting:
- Internal Sorting: All records fit inside main memory (RAM) simultaneously (e.g., Quick sort, Heap sort, Insertion sort).
- External Sorting: Dataset exceeds RAM capacity and resides on secondary disk storage, sorted via memory-sized runs and multi-way merging (e.g., External Merge Sort).
Quick Sort Algorithm:
Algorithm QUICKSORT(A, low, high):
1. If low < high:
p = PARTITION(A, low, high)
QUICKSORT(A, low, p - 1)
QUICKSORT(A, p + 1, high)
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]; Return jTrace on [5, 43, 99, 20, 45, 7, 6, 63, 92, 4]:
- Pivot
5:istops at43,jstops at4(index 9). Swap43&4[5, 4, 99, ..., 43]; thenicrossesj(j=1). Swap5&4[4] [5] [99, 20, 45, 7, 6, 63, 92, 43]. - Right
[99, 20, 45, 7, 6, 63, 92, 43], Pivot99:ireaches end,jat43. Swap99&43[43, 20, 45, 7, 6, 63, 92] [99]. - Pivot
43: swap45&6[43, 20, 6, 7, 45, 63, 92]; swap43&7[7, 20, 6] [43] [45, 63, 92]. - Left
[7, 20, 6], Pivot7: swap20&6[7, 6, 20]; swap7&6[6] [7] [20]. - Right
[45, 63, 92], Pivot45: stays at start[45] [63, 92]; pivot63stays[63, 92].
Combined sorted list: [4, 5, 6, 7, 20, 43, 45, 63, 92, 99].
Answer:
Sorted sequence via quick sort: 4, 5, 6, 7, 20, 43, 45, 63, 92, 99.