Shell Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Shell Sort with gap sequence halving

What is the output of the following Rust code that performs Shell Sort on the array?

DSA Rust

fn shell_sort(arr: &mut [i32]) {
    let n = arr.len();
    let mut gap = n / 2;
    while gap > 0 {
        for i in gap..n {
            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;
    }
}

fn main() {
    let mut data = [23, 12, 1, 8, 34, 54, 2, 3];
    shell_sort(&mut data);
    println!("{:?}", data);
}

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

Think about how Shell Sort reduces the gap and sorts subarrays.

Shell Sort starts with a large gap and reduces it, sorting elements far apart first. This leads to a fully sorted array at the end.

🧠 Conceptual

intermediate

Understanding the gap sequence in Shell Sort

In Shell Sort, what is the main purpose of using a gap sequence that decreases over time?

A To sort the array only partially and leave some elements unsorted

B To compare and swap elements that are far apart first, reducing disorder quickly

C To increase the number of swaps needed by comparing adjacent elements only

D To skip sorting smaller subarrays and focus on the largest elements only

💡 Hint

Think about how sorting distant elements first helps overall sorting.

The gap sequence allows Shell Sort to move elements closer to their correct position faster by comparing elements far apart, which reduces disorder efficiently before finishing with smaller gaps.

🔧 Debug

advanced

Identify the error in this Shell Sort implementation

What error will this Rust Shell Sort code produce when run?

DSA Rust

fn shell_sort(arr: &mut [i32]) {
    let n = arr.len();
    let mut gap = n / 2;
    while gap > 0 {
        for i in gap..n {
            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 /= 0;
    }
}

fn main() {
    let mut data = [5, 3, 8, 6, 2];
    shell_sort(&mut data);
    println!("{:?}", data);
}

A Compilation error due to missing semicolon

B Index out of bounds panic when accessing arr[j - gap]

C Panic due to division by zero at gap /= 0

D No error, outputs sorted array

💡 Hint

Look carefully at how gap is updated inside the loop.

The line gap /= 0 causes a division by zero panic at runtime, which crashes the program.

📝 Syntax

advanced

Syntax error in Shell Sort Rust code

Which option contains the correct syntax to declare and initialize the gap variable for Shell Sort in Rust?

A let mut gap = n / 2;

B let gap := n / 2;

C var gap = n / 2;

D gap = n / 2;

💡 Hint

Remember Rust variable declaration syntax.

In Rust, variables are declared with let, optionally mutable with mut, and use = for assignment. Other options use syntax from other languages or are incomplete.

🚀 Application

expert

Shell Sort performance on nearly sorted array

Given a nearly sorted array of 1,000 elements, which statement best describes Shell Sort's performance compared to simple insertion sort?

A Shell Sort will generally perform faster because it moves elements over larger gaps first, reducing total shifts

B Insertion sort will always be faster because the array is nearly sorted

C Both algorithms perform the same because they use similar comparisons

D Shell Sort will be slower because it does unnecessary comparisons with large gaps

💡 Hint

Think about how Shell Sort handles distant elements compared to insertion sort.

Shell Sort improves on insertion sort by moving elements over large gaps early, which reduces the total number of shifts even in nearly sorted arrays, often leading to better performance.

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