PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

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:

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 j

Trace on [5, 43, 99, 20, 45, 7, 6, 63, 92, 4]:

  1. Pivot 5: i stops at 43, j stops at 4 (index 9). Swap 43 & 4 [5, 4, 99, ..., 43]; then i crosses j (j=1). Swap 5 & 4 [4] [5] [99, 20, 45, 7, 6, 63, 92, 43].
  2. Right [99, 20, 45, 7, 6, 63, 92, 43], Pivot 99: i reaches end, j at 43. Swap 99 & 43 [43, 20, 45, 7, 6, 63, 92] [99].
  3. Pivot 43: swap 45 & 6 [43, 20, 6, 7, 45, 63, 92]; swap 43 & 7 [7, 20, 6] [43] [45, 63, 92].
  4. Left [7, 20, 6], Pivot 7: swap 20 & 6 [7, 6, 20]; swap 7 & 6 [6] [7] [20].
  5. Right [45, 63, 92], Pivot 45: stays at start [45] [63, 92]; pivot 63 stays [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.

All past exam questions for Data Structure and Algorithms