PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Write the algorithm of the quick sort including the steps of partition. Discuss the complexity of this algorithm.

Solution

Quick Sort and Partition 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]
2. i = low + 1, j = high
3. 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]
4. Swap A[low] and A[j]
5. Return j

Time and Space Complexity Analysis of Quick Sort:

  1. Best Case & Average Case — : When the pivot splits the array into roughly equal halves (), the recurrence is , which solves to via the Master Theorem.
  2. Worst Case — : When the input is already sorted or reverse-sorted and the first/last element is chosen as pivot, partitions produce sizes and : .
  3. Space Complexity: In-place partitioning uses heap space, while recursion stack depth uses average space and worst-case space.
Answer:

Quick sort partitions elements around a pivot in per level and recurses on left/right subarrays. Complexity is best/average time, worst-case time, and average stack space.

All past exam questions for Data Structure and Algorithms