Shell Sort Algorithm in DSA Rust - 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 good choice because it improves on simple sorting methods by comparing elements far apart first, then gradually reducing the gap.

🎯 Goal: Build a Rust program that sorts a list of numbers using the Shell Sort algorithm step-by-step.

📋 What You'll Learn

Create a vector of integers with exact values

Define a gap variable for the sorting steps

Implement the Shell Sort logic using nested loops

Print the sorted vector as the final output

💡 Why This Matters

🌍 Real World

Shell Sort is used in systems where moderate sorting speed is needed with simple implementation, such as embedded systems or small datasets.

💼 Career

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

1

Create the initial vector

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

DSA Rust

# Create the vector 'numbers' with the given integers
# Your code here

Hint

Use let mut numbers = vec![23, 12, 1, 8, 34, 54, 2, 3]; to create the vector.

2

Set the initial gap value

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

DSA Rust

fn main() {
    let mut numbers = vec![23, 12, 1, 8, 34, 54, 2, 3];
    // Set the initial gap value
    // Your code here
}

Hint

Use let mut gap = numbers.len() / 2; to set the gap.

3

Implement the Shell Sort logic

Write a while loop that runs while gap > 0. Inside it, write a for loop with i from gap to numbers.len(). Inside the for loop, create a variable temp equal to numbers[i]. Then create a mutable variable j equal to i. Use a while loop that runs while j >= gap and numbers[j - gap] > temp. Inside this loop, set numbers[j] to numbers[j - gap] and subtract gap from j. After the inner loop, set numbers[j] to temp. Finally, update gap by dividing it by 2.

DSA Rust

fn main() {
    let mut numbers = vec![23, 12, 1, 8, 34, 54, 2, 3];
    let mut gap = numbers.len() / 2;
    // Implement Shell Sort logic here
    // Your code here
}

Hint

Use nested loops and update numbers by shifting elements and inserting temp in the correct place.

4

Print the sorted vector

Add a println! statement to print the sorted numbers vector after the sorting is complete.

DSA Rust

fn main() {
    let mut numbers = vec![23, 12, 1, 8, 34, 54, 2, 3];
    let mut gap = numbers.len() / 2;
    while gap > 0 {
        for i in gap..numbers.len() {
            let temp = numbers[i];
            let mut j = i;
            while j >= gap && numbers[j - gap] > temp {
                numbers[j] = numbers[j - gap];
                j -= gap;
            }
            numbers[j] = temp;
        }
        gap /= 2;
    }
    // Print the sorted vector
    // Your code here
}

Hint

Use println!("{:?}", numbers); to print the vector.

Practice

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

easy

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

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

C. It uses a divide and conquer approach like merge sort.

D. It sorts elements by inserting each element into a sorted sublist one by one.

Solution

1. Step 1: Understand Shell Sort's approach

   Shell sort starts by comparing elements far apart and reduces the gap over iterations.

2. Step 2: Compare with other sorting methods

   Unlike bubble or insertion sort, it uses gaps to improve efficiency before final insertion sort pass.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based comparison [OK]

Hint: Shell sort uses gaps that shrink over time [OK]

Common Mistakes:

• Confusing Shell sort with bubble sort
• Thinking it only swaps adjacent elements
• Assuming it uses divide and conquer

2. Which of the following is the correct Rust syntax to start the gap value in Shell Sort for an array named arr?

easy

A. let mut gap = arr.len() + 1;

B. let gap = arr.len() * 2;

C. let mut gap = arr.len() / 2;

D. let gap = arr.len() - 1;

Solution

1. Step 1: Identify how gap is initialized in Shell Sort

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

2. Step 2: Check Rust syntax correctness

   Using let mut gap = arr.len() / 2; correctly initializes a mutable gap variable with half the length.

3. Final Answer:

   let mut gap = arr.len() / 2; -> Option C

4. Quick Check:

   Gap starts at half length [OK]

Hint: Gap starts at half array length in Shell Sort [OK]

Common Mistakes:

• Using multiplication instead of division for gap
• Not declaring gap as mutable
• Starting gap at array length or length minus one

3. What will be the output of the following Rust code snippet after applying one full pass of Shell Sort with initial gap 3 on arr = [9, 8, 3, 7, 5, 6, 4, 1]?

let mut arr = vec![9, 8, 3, 7, 5, 6, 4, 1];
let gap = 3;
for i in gap..arr.len() {
    let temp = arr[i];
    let mut j = i;
    while j >= gap && arr[j - gap] > temp {
        arr[j] = arr[j - gap];
        j -= gap;
    }
    arr[j] = temp;
}
println!("{:?}", arr);

medium

A. [4, 1, 3, 7, 5, 6, 9, 8]

B. [7, 8, 3, 9, 5, 6, 4, 1]

C. [9, 8, 3, 7, 5, 6, 4, 1]

D. [1, 8, 3, 7, 5, 6, 4, 9]

Solution

1. Step 1: Perform insertion with gap 3 on elements from index 3 to end

   Start at i=3 (value 7), compare with arr[0]=9, since 9 > 7, shift 9 to index 3 and place 7 at index 0.

2. Step 2: Repeat for i=4 to 7

   i=4 (5) compares with arr[1]=8, shift 8 to 4, place 5 at 1; i=5 (6) compares with arr[2]=3 no shift; i=6 (4) compares with arr[3]=9 shifted to 6, then arr[0]=7 shifted to 3, place 4 at 0; i=7 (1) compares with arr[4]=8 shifted to 7, arr[1]=5 shifted to 4, place 1 at 1.

3. Final Answer:

   [4, 1, 3, 7, 5, 6, 9, 8] -> Option A

4. Quick Check:

   After gap 3 pass = [4,1,3,7,5,6,9,8] [OK]

Hint: Trace insertion with gap 3 step-by-step [OK]

Common Mistakes:

• Not shifting elements correctly with gap
• Confusing indices during insertion
• Assuming no change after first pass

4. Identify the bug in this Rust Shell Sort snippet and choose the correct fix:

let mut gap = arr.len() / 2;
while gap > 0 {
    for i in gap..arr.len() {
        let temp = arr[i];
        let mut j = i;
        while j >= gap && arr[j - gap] < temp {
            arr[j] = arr[j - gap];
            j -= gap;
        }
        arr[j] = temp;
    }
    gap /= 2;
}

medium

A. Change gap /= 2; to gap *= 2; to increase gap.

B. Change arr[j - gap] < temp to arr[j - gap] > temp in inner while condition.

C. Initialize gap as arr.len() instead of half.

D. Remove the inner while loop completely.

Solution

1. Step 1: Analyze the inner while condition

   The condition arr[j - gap] < temp causes sorting in descending order, but Shell Sort usually sorts ascending.

2. Step 2: Correct the comparison for ascending order

   Changing it to arr[j - gap] > temp ensures elements larger than temp shift right, sorting ascending.

3. Final Answer:

   Change arr[j - gap] < temp to arr[j - gap] > temp in inner while condition. -> Option B

4. Quick Check:

   Comparison sign fixes sorting order [OK]

Hint: Check comparison signs for correct ascending order [OK]

Common Mistakes:

• Using wrong comparison sign for sorting order
• Changing gap update incorrectly
• Removing essential loops

5. Given a large array with many duplicate values, how can you modify the Shell Sort algorithm in Rust to improve efficiency and maintain stable sorting (preserving order of equal elements)?

hard

A. Increase the gap size each iteration and swap all equal elements aggressively.

B. Remove the gap loop and sort only once with bubble sort.

C. Use a simple gap of 1 only and rely on standard insertion sort.

D. Use a gap sequence like Tokuda's and modify insertion to avoid swapping equal elements.

Solution

1. Step 1: Understand gap sequences impact

   Using advanced gap sequences like Tokuda's improves efficiency by reducing comparisons and swaps.

2. Step 2: Modify insertion to maintain stability

   Avoid swapping equal elements during insertion to keep their original order, preserving stability.

3. Final Answer:

   Use a gap sequence like Tokuda's and modify insertion to avoid swapping equal elements. -> Option D

4. Quick Check:

   Advanced gaps + stable insertion = better Shell Sort [OK]

Hint: Use smart gaps and stable insertion for duplicates [OK]

Common Mistakes:

• Increasing gap size instead of decreasing
• Ignoring stability in sorting equal elements
• Using only gap=1 which is slow
• Replacing Shell Sort with bubble sort