PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

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 j

First Partition on [30, 25, 79, 19, 48, 28, 21, 44, 120] (pivot = 30):

Recursive Calls on Left Subarray [28, 25, 21, 19]:

Recursive Calls on Right Subarray [48, 79, 44, 120]:

Answer:

Sorted sequence using quick sort:

All past exam questions for Data Structure and Algorithms