PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Explain shell sort. Sort the numbers 92, 83, 22, 49, 36, 98, 12, 9, 70 and 51 using shell sort.

Solution

Working Principle of Shell Sort: Shell sort generalizes insertion sort by comparing and shifting elements separated by a decreasing gap sequence (typically ). Earlier large-gap passes move out-of-place items rapidly toward their destinations so the final gap = 1 insertion sort runs on a nearly sorted array.

Shell Sort Trace on ([92, 83, 22, 49, 36, 98, 12, 9, 70, 51]): Using Shell's gap sequence :

  1. Pass 1 (gap = 5): Compare pairs (i, i+5):
    • (92, 98) ok
    • (83, 12) swap 12, 83
    • (22, 9) swap 9, 22
    • (49, 70) ok
    • (36, 51) ok
    • Array after gap = 5: [92, 12, 9, 49, 36, 98, 83, 22, 70, 51]
  2. Pass 2 (gap = 2): Insertion sort on even indices {92, 9, 36, 83, 70} and odd indices {12, 49, 98, 22, 51}:
    • Even indices sorted {9, 36, 70, 83, 92}
    • Odd indices sorted {12, 22, 49, 51, 98}
    • Array after gap = 2: [9, 12, 36, 22, 70, 49, 83, 51, 92, 98]
  3. Pass 3 (gap = 1): Standard insertion sort:
    • 22 shifts past 36; 49 shifts past 70; 51 shifts past 83, 70.
    • Final sorted array: [9, 12, 22, 36, 49, 51, 70, 83, 92, 98].
Answer:

Shell sort performs gapped insertion sorts across shrinking gaps (), producing the sorted sequence: 9, 12, 22, 36, 49, 51, 70, 83, 92, 98.

All past exam questions for Data Structure and Algorithms