Past exam question: 2078 Chaitra (Regular), Q8
Open in the Padhaiko appQuestion
Write an algorithm for quick sort. Sort the following numbers using quick sort: 30, 25, 79, 19, 48, 28, 21, 44 and 120.
Solution
Quick Sort and Partition Algorithm (First-Element Pivot):
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]
4. Return jFirst Partition on [30, 25, 79, 19, 48, 28, 21, 44, 120] (pivot = 30):
istops at79(),jstops at21(). Swap79and21:[30, 25, 21, 19, 48, 28, 79, 44, 120].istops at48,jstops at28. Swap48and28:[30, 25, 21, 19, 28, 48, 79, 44, 120].- Next
ipassesj(i=5, j=4). Swap pivot30withA[4]=28:[28, 25, 21, 19] [30] [48, 79, 44, 120].
Recursive Calls on Left Subarray [28, 25, 21, 19]:
- Pivot
28:ireaches end (i=4),j=3(19). Swap28and19:[19, 25, 21] [28]. - On
[19, 25, 21], pivot19:istops at25,jcrosses to index0. Pivot19stays at index0:[19] [25, 21]. - On
[25, 21], pivot25: swap25and21[21, 25]. - Left half sorted:
[19, 21, 25, 28].
Recursive Calls on Right Subarray [48, 79, 44, 120]:
- Pivot
48:istops at79,jstops at44. Swap79and44:[48, 44, 79, 120]. - Next
ipassesj(jat44). Swap pivot48and44:[44] [48] [79, 120]. - On
[79, 120], pivot79:jstops at79, stays in place[79, 120]. - Combine all sorted partitions:
[19, 21, 25, 28, 30, 44, 48, 79, 120].
Answer:
Sorted sequence using quick sort: