Shell Sort Algorithm in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the gap for Shell Sort.

DSA Rust

let mut gap = [1] / 2;

Drag options to blanks, or click blank then click option'

Aarr.len() - 1

Barr.len()

Carr.len() * 2

Darr.len() / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr.len() / 2 which makes the gap a quarter of the length.

Using length minus one which is off by one.

Shell Sort starts with a gap of half the array length.

2fill in blank

medium

Complete the code to reduce the gap in each iteration.

DSA Rust

gap = [1] / 2;

Drag options to blanks, or click blank then click option'

Agap

Barr.len()

Cgap / 2

Dgap - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the array length again instead of the current gap.

Subtracting 1 instead of dividing.

The gap is reduced by half each time until it reaches zero.

3fill in blank

hard

Fix the error in the inner loop condition to avoid index out of bounds.

DSA Rust

while j >= [1] && arr[j - [1]] > temp {

Drag options to blanks, or click blank then click option'

Aarr.len()

B1

C0

Dgap

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 or 0 causing index underflow.

Using array length which is too large.

The loop checks elements gap positions behind, so j must be at least gap.

4fill in blank

hard

Fill both blanks to correctly shift elements during insertion sort step.

DSA Rust

arr[j] = arr[j [1] [2]];

Drag options to blanks, or click blank then click option'

A-

B+

Cgap

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction.

Using 1 instead of gap for shifting.

Elements are shifted by subtracting the gap to move them forward.

5fill in blank

hard

Fill all three blanks to complete the insertion of temp element.

DSA Rust

let mut j = i; while j >= [1] && arr[j - [2]] > temp { arr[j] = arr[j - [3]]; j -= [3]; } arr[j] = temp;

Drag options to blanks, or click blank then click option'

Agap

B1

Darr.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of gap causing wrong shifts.

Using array length causing index errors.

The insertion shifts elements by gap until the right position is found.

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