PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

What is internal and external sorting? Write an algorithm for shell sort.

Solution

Internal vs. External Sorting:

Algorithm for Shell Sort:

Algorithm SHELL_SORT(A, n):
1. gap = floor(n / 2)
2. While gap > 0:
       For i = gap to n - 1:
           temp = A[i]
           j = i
           While j >= gap and A[j - gap] > temp:
               A[j] = A[j - gap]
               j = j - gap
           A[j] = temp
       gap = floor(gap / 2)
Answer:

Internal sorting operates inside RAM; external sorting handles disk-resident data exceeding RAM. Shell sort runs gapped insertion passes with gap halving from down to 1.

All past exam questions for Data Structure and Algorithms