Shell Sort Algorithm in DSA Go - Build from Scratch

Shell Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Shell Sort is a sorting technique that improves on simple sorting by comparing elements far apart and gradually reducing the gap.Imagine you have a messy stack of books with different thicknesses, and you want to arrange them from thinnest to thickest quickly by comparing books that are far apart first, then closer and closer.

🎯 Goal: Build a Go program that sorts a slice of integers using the Shell Sort algorithm step-by-step.

📋 What You'll Learn

Create a slice of integers with exact values

Define a gap variable for the Shell Sort

Implement the Shell Sort logic using nested loops

Print the sorted slice at the end

💡 Why This Matters

🌍 Real World

Shell Sort is useful for sorting medium-sized lists efficiently in systems where simple sorting is too slow but full advanced algorithms are not needed.

💼 Career

Understanding Shell Sort helps in grasping sorting algorithm concepts and improving problem-solving skills for coding interviews and software development.

1

Create the initial slice of integers

Create a slice called numbers with these exact integers in order: 23, 12, 1, 8, 34, 54, 2, 3

DSA Go

// Create the slice called numbers with the exact integers
// Your code here

Hint

Use numbers := []int{23, 12, 1, 8, 34, 54, 2, 3} to create the slice.

2

Set the initial gap for Shell Sort

Add a variable called gap and set it to half the length of numbers using len(numbers) / 2

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{23, 12, 1, 8, 34, 54, 2, 3}
    // Set the initial gap
    // Your code here
}

Hint

Use gap := len(numbers) / 2 to start the gap.

3

Implement the Shell Sort core logic

Write a for loop that runs while gap > 0. Inside it, write a for loop with i := gap to i < len(numbers). Inside that, set temp := numbers[i] and j := i. Then use a for loop to shift elements while j >= gap and numbers[j - gap] > temp. After shifting, set numbers[j] = temp. Finally, reduce gap by half at the end of the outer loop.

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{23, 12, 1, 8, 34, 54, 2, 3}
    gap := len(numbers) / 2

    // Implement Shell Sort loops here
    // Your code here
}

Hint

Use nested loops to compare and shift elements based on the gap, then reduce the gap each time.

4

Print the sorted slice

Add a fmt.Println(numbers) statement after the sorting loops to print the sorted slice.

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{23, 12, 1, 8, 34, 54, 2, 3}
    gap := len(numbers) / 2

    for gap > 0 {
        for i := gap; i = gap && numbers[j-gap] > temp {
                numbers[j] = numbers[j-gap]
                j -= gap
            }
            numbers[j] = temp
        }
        gap /= 2
    }

    // Print the sorted slice
    // Your code here
}

Hint

Use fmt.Println(numbers) to display the sorted slice.

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