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).