Shell Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

Perform gapped insertion sort

↓

Reduce gap: gap = gap/2

↓

Is gap > 0?

No→Sorted array

↩Back to gapped insertion sort

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap until it becomes 1, finishing with a normal insertion sort.

Execution Sample

DSA Go

arr := []int{5, 3, 8, 1, 2}
gap := len(arr)/2
for gap > 0 {
  // gapped insertion sort
  gap /= 2
}

This code sorts the array using Shell Sort by repeatedly reducing the gap and sorting elements at that gap.

Execution Table

Step	Operation	Gap	Array State	Comparison	Swap?	Description
1	Initialize gap	2	[5, 3, 8, 1, 2]	-	-	Set gap to 2 (5/2)
2	Compare arr[2] and arr[0]	2	[5, 3, 8, 1, 2]	8 vs 5	No	8 >= 5, no swap
3	Compare arr[3] and arr[1]	2	[5, 3, 8, 1, 2]	1 vs 3	Yes	1 < 3, swap
4	Array after swap	2	[5, 1, 8, 3, 2]	-	-	Array updated after swap
5	Compare arr[4] and arr[2]	2	[5, 1, 8, 3, 2]	2 vs 8	Yes	2 < 8, swap
6	Array after swap	2	[5, 1, 2, 3, 8]	-	-	Array updated after swap
7	Reduce gap	1	[5, 1, 2, 3, 8]	-	-	Gap reduced to 1
8	Compare arr[1] and arr[0]	1	[5, 1, 2, 3, 8]	1 vs 5	Yes	1 < 5, swap
9	Array after swap	1	[1, 5, 2, 3, 8]	-	-	Array updated after swap
10	Compare arr[2] and arr[1]	1	[1, 5, 2, 3, 8]	2 vs 5	Yes	2 < 5, swap
11	Array after swap	1	[1, 2, 5, 3, 8]	-	-	Array updated after swap
12	Compare arr[3] and arr[2]	1	[1, 2, 5, 3, 8]	3 vs 5	Yes	3 < 5, swap
13	Array after swap	1	[1, 2, 3, 5, 8]	-	-	Array updated after swap
14	Compare arr[4] and arr[3]	1	[1, 2, 3, 5, 8]	8 vs 5	No	8 >= 5, no swap
15	Reduce gap	0	[1, 2, 3, 5, 8]	-	-	Gap reduced to 0, sorting done

💡 Gap becomes 0, so the array is fully sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 7	After Step 15
gap	undefined	2	1	0
arr	[5, 3, 8, 1, 2]	[5, 3, 8, 1, 2]	[5, 1, 2, 3, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we start with a gap of n/2 instead of 1?

Starting with a larger gap allows the algorithm to move elements far apart closer to their correct position early, reducing total swaps later. See Step 1 where gap is 2, not 1.

Why do we perform insertion sort on elements separated by the gap?

Gapped insertion sort sorts elements that are 'gap' apart, partially sorting the array. This helps reduce disorder before the final pass with gap=1. See Steps 2-6 for gap=2 sorting.

Why does the gap reduce by dividing by 2 each time?

Reducing gap by half each time gradually refines the sorting from coarse to fine. This sequence is simple and effective. See Steps 7 and 15 where gap changes from 2 to 1 to 0.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after Step 6?

A [5, 1, 8, 3, 2]

B [5, 1, 2, 3, 8]

C [1, 3, 8, 5, 2]

D [5, 3, 8, 1, 2]

💡 Hint

Check the 'Array after swap' row at Step 6 in the execution table.

At which step does the gap become 1?

A Step 1

B Step 7

C Step 15

D Step 2

💡 Hint

Look for the 'Reduce gap' operation in the execution table.

If the initial gap was set to 1, what would happen?

A The array would be sorted immediately with normal insertion sort.

B The algorithm would skip sorting.

C The gap would increase automatically.

D The array would remain unsorted.

💡 Hint

Gap=1 means normal insertion sort, as shown in Steps 7-14.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Perform insertion sort on elements gap apart
- Reduce gap by half each iteration
- Repeat until gap = 0
- Final pass with gap=1 is normal insertion sort
- Efficient for medium-sized arrays

Full Transcript

Shell Sort sorts an array by starting with a large gap between elements and sorting those elements. The gap starts at half the array size and reduces by half each time. At each gap, a gapped insertion sort is performed, moving elements closer to their correct positions. When the gap reaches 1, a normal insertion sort finishes the sorting. This method reduces the total number of swaps compared to simple insertion sort, making it faster for medium-sized arrays.

Practice

1. What is the main idea behind the Shell Sort Algorithm?

easy

A. It uses a divide and conquer approach to split and merge arrays.

B. It sorts elements by repeatedly swapping adjacent elements only.

C. It sorts elements by comparing distant elements and gradually reducing the gap.

D. It builds a sorted array by inserting elements one by one in order.

Solution

1. Step 1: Understand Shell Sort concept

   Shell Sort improves insertion sort by comparing elements far apart, reducing the gap over iterations.

2. Step 2: Compare with other sorting methods

   Unlike bubble or insertion sort, Shell Sort starts with distant comparisons, not just adjacent swaps.

3. Final Answer:

   It sorts elements by comparing distant elements and gradually reducing the gap. -> Option C

4. Quick Check:

   Shell Sort = distant comparisons + gap reduction [OK]

Hint: Shell Sort uses gaps to compare far elements first [OK]

Common Mistakes:

• Thinking Shell Sort only swaps adjacent elements
• Confusing Shell Sort with merge or quick sort
• Assuming it inserts elements one by one without gaps

2. Which of the following is the correct way to initialize the gap variable in Shell Sort in Go?

easy

A. gap = len(arr) * 2

B. gap := len(arr) / 2

C. gap := 0

D. gap = len(arr) + 1

Solution

1. Step 1: Identify gap initialization in Shell Sort

   The gap usually starts as half the array length to compare distant elements first.

2. Step 2: Check Go syntax for variable initialization

   Using gap := len(arr) / 2 correctly declares and initializes gap in Go.

3. Final Answer:

   gap := len(arr) / 2 -> Option B

4. Quick Check:

   gap = half array length [OK]

Hint: Start gap as half array length in Go [OK]

Common Mistakes:

• Using gap larger than array length
• Initializing gap to zero which stops sorting
• Incorrect Go syntax for variable declaration

3. What will be the output of the following Go code snippet using Shell Sort on array [9, 8, 3, 7, 5]?

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
    }
    return arr
}

fmt.Println(shellSort([]int{9, 8, 3, 7, 5}))

medium

A. [3 5 7 8 9]

B. [9 8 7 5 3]

C. [5 3 7 8 9]

D. [3 7 5 8 9]

Solution

1. Step 1: Trace first gap iteration (gap=2)

   Compare elements 2 apart and sort: array changes from [9,8,3,7,5] to [3,8,9,7,5] then [3,5,9,7,8].

2. Step 2: Trace second gap iteration (gap=1)

   Standard insertion sort on nearly sorted array results in [3,5,7,8,9].

3. Final Answer:

   [3 5 7 8 9] -> Option A

4. Quick Check:

   Shell Sort output = sorted array [OK]

Hint: Shell Sort outputs sorted array [OK]

Common Mistakes:

• Confusing gap steps and final output
• Assuming no change after first gap
• Mixing up array indices during swaps

4. Identify the error in this Go Shell Sort code snippet:

func shellSort(arr []int) {
    n := len(arr)
    gap := n / 2
    for gap > 0 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] < temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap /= 2
    }
}

medium

A. The gap should increase instead of decrease.

B. The outer loop should use for gap < n instead of gap > 0.

C. The variable temp is not initialized properly.

D. The comparison operator should be > instead of < in inner loop.

Solution

1. Step 1: Analyze inner loop comparison

   The inner loop compares arr[j-gap] and temp to decide swapping. It should move larger elements up, so condition must be arr[j-gap] > temp.

2. Step 2: Check current comparison operator

   Current code uses arr[j-gap] < temp which incorrectly moves smaller elements, breaking sort order.

3. Final Answer:

   The comparison operator should be > instead of < in inner loop. -> Option D

4. Quick Check:

   Correct comparison = > [OK]

Hint: Inner loop compares if previous element is greater [OK]

Common Mistakes:

• Using < instead of > in inner loop condition
• Increasing gap instead of decreasing
• Misplacing gap update outside loop

5. Given an array with many duplicate values, how can Shell Sort be adapted to maintain stable sorting (preserving original order of equal elements)?

hard

A. Use a stable gap sequence like Hibbard's sequence and avoid swapping equal elements.

B. Increase the gap size to skip duplicates during sorting.

C. Shell Sort cannot be made stable; use a different algorithm instead.

D. Modify the inner loop to use >= instead of > when comparing elements.

Solution

1. Step 1: Understand stability in sorting

   Stable sorting means equal elements keep their original order after sorting.

2. Step 2: Adapt Shell Sort for stability

   Using a stable gap sequence like Hibbard's and avoiding swaps when elements are equal helps maintain stability.

3. Step 3: Evaluate other options

   Using >= breaks stability, increasing gap skips elements, and claiming impossibility is incorrect.

4. Final Answer:

   Use a stable gap sequence like Hibbard's sequence and avoid swapping equal elements. -> Option A

5. Quick Check:

   Stable Shell Sort = stable gaps + no equal swaps [OK]

Hint: Use stable gap sequences and skip swapping equals [OK]

Common Mistakes:

• Using >= comparison breaking stability
• Assuming Shell Sort cannot be stable
• Increasing gap size to skip duplicates