Shell Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Shell Sort on a small array

What is the output of the following Go code after applying Shell Sort on the array?

DSA Go

package main
import "fmt"

func shellSort(arr []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
        }
    }
}

func main() {
    arr := []int{23, 12, 1, 8, 34, 54, 2, 3}
    shellSort(arr)
    fmt.Println(arr)
}

A [54 34 23 12 8 3 2 1]

B [1 3 2 8 12 23 34 54]

C [23 12 1 8 34 54 2 3]

D [1 2 3 8 12 23 34 54]

💡 Hint

Shell Sort sorts by comparing elements far apart and gradually reducing the gap.

Shell Sort starts with a large gap and sorts elements that are far apart. It reduces the gap until it becomes 1, performing a final insertion sort. The final sorted array is in ascending order.

🧠 Conceptual

intermediate

Gap sequence in Shell Sort

Which of the following gap sequences is used in the provided Shell Sort implementation?

A Start with 1 and multiply by 2 each time

B Use prime numbers as gaps

C Start with n/2 and keep dividing by 2 until gap is 0

D Use Fibonacci numbers as gaps

💡 Hint

Look at how the gap variable changes in the code.

The code starts with gap = n/2 and divides gap by 2 each iteration until gap becomes 0.

🔧 Debug

advanced

Identify the error in this Shell Sort variant

What error will this Go code produce when running the Shell Sort variant?

DSA Go

package main
import "fmt"

func shellSort(arr []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 >= 0 && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
    }
}

func main() {
    arr := []int{5, 3, 8, 6, 2}
    shellSort(arr)
    fmt.Println(arr)
}

A Index out of range runtime panic

B [2 3 5 6 8]

C [5 3 8 6 2]

D Compilation error

💡 Hint

Check the condition in the inner loop comparing j and gap.

The inner loop condition uses 'j >= 0' instead of 'j >= gap', causing an index out of range panic when j-gap < 0.

❓ Predict Output

advanced

Shell Sort output with negative and positive numbers

What is the output of the following Go code after sorting?

DSA Go

package main
import "fmt"

func shellSort(arr []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
        }
    }
}

func main() {
    arr := []int{-3, 0, 2, -1, 5, -2}
    shellSort(arr)
    fmt.Println(arr)
}

A [-3 -2 -1 0 2 5]

B [-3 -1 -2 0 2 5]

C [5 2 0 -1 -2 -3]

D [-2 -3 -1 0 2 5]

💡 Hint

Shell Sort sorts in ascending order regardless of negative or positive values.

The algorithm sorts all numbers from smallest to largest, including negatives.

🧠 Conceptual

expert

Time complexity of Shell Sort depends on gap sequence

Which statement about Shell Sort's time complexity is correct?

A Time complexity is always O(n log n) regardless of gap sequence

B Time complexity can vary from O(n^2) to O(n^(3/2)) depending on gap sequence

C Time complexity is always O(n^2) for any gap sequence

D Time complexity is O(n) if the array is already sorted

💡 Hint

Different gap sequences affect how quickly the array becomes sorted.

Shell Sort's time complexity depends on the gap sequence. Some sequences give O(n^(3/2)) or better, while others degrade to O(n^2).

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