Past exam question: 2075 Baisakh (Back), Q7
Open in the Padhaiko appQuestion
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 :
- Pass 1 (
gap = 5): Compare pairs(i, i+5):(92, 98)ok(83, 12)swap12, 83(22, 9)swap9, 22(49, 70)ok(36, 51)ok- Array after
gap = 5:[92, 12, 9, 49, 36, 98, 83, 22, 70, 51]
- 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]
- Even indices sorted
- Pass 3 (
gap = 1): Standard insertion sort:22shifts past36;49shifts past70;51shifts past83, 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.