Shell Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

For gap down to 1

↓

Perform gapped insertion sort

↓

Reduce gap (gap = gap/2)

↓

If gap == 0, array sorted

↓

End

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap until it becomes 1, finishing with a normal insertion sort.

Execution Sample

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;
    }
}

This code sorts an array using Shell Sort by repeatedly sorting elements with decreasing gaps.

Execution Table

Step	Operation	Gap	Index i	Index j	Array State	Action
1	Initialize	5/2=2	-	-	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]	Set gap=2
2	Outer loop start	2	2	-	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]	Start i=2
3	Compare arr[j-gap] and temp	2	2	2	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]	temp=1, arr[0]=23 > 1, shift arr[0] to arr[2]
4	Shift	2	2	0	[23, 12, 23, 8, 34, 54, 2, 3, 7, 4]	j=0
5	Insert temp	2	2	0	[1, 12, 23, 8, 34, 54, 2, 3, 7, 4]	Insert 1 at arr[0]
6	Next i	2	3	3	[1, 12, 23, 8, 34, 54, 2, 3, 7, 4]	temp=8, arr[1]=12 > 8? No, insert 8 at arr[3]
7	Next i	2	4	4	[1, 12, 23, 8, 34, 54, 2, 3, 7, 4]	temp=34, arr[2]=23 > 34? No, insert 34 at arr[4]
8	Next i	2	5	5	[1, 12, 23, 8, 34, 54, 2, 3, 7, 4]	temp=54, arr[3]=8 > 54? No, insert 54 at arr[5]
9	Next i	2	6	6	[1, 12, 23, 8, 34, 54, 2, 3, 7, 4]	temp=2, arr[4]=34 > 2, shift arr[4] to arr[6]
10	Shift	2	6	4	[1, 12, 23, 8, 34, 54, 34, 3, 7, 4]	j=4
11	Compare	2	6	2	[1, 12, 23, 8, 34, 54, 34, 3, 7, 4]	arr[2]=23 > 2, shift arr[2] to arr[4]
12	Shift	2	6	2	[1, 12, 23, 8, 23, 54, 34, 3, 7, 4]	j=2
13	Compare	2	6	0	[1, 12, 23, 8, 23, 54, 34, 3, 7, 4]	arr[0]=1 > 2? No, insert 2 at arr[2]
14	Insert	2	6	2	[1, 12, 2, 8, 23, 54, 34, 3, 7, 4]	Insert 2 at arr[2]
15	Next i	2	7	7	[1, 12, 2, 8, 23, 54, 34, 3, 7, 4]	temp=3, arr[5]=54 > 3, shift arr[5] to arr[7]
16	Shift	2	7	5	[1, 12, 2, 8, 23, 54, 34, 54, 7, 4]	j=5
17	Compare	2	7	3	[1, 12, 2, 8, 23, 54, 34, 54, 7, 4]	arr[3]=8 > 3, shift arr[3] to arr[5]
18	Shift	2	7	3	[1, 12, 2, 8, 23, 8, 34, 54, 7, 4]	j=3
19	Compare	2	7	1	[1, 12, 2, 8, 23, 8, 34, 54, 7, 4]	arr[1]=12 > 3, shift arr[1] to arr[3]
20	Shift	2	7	1	[1, 12, 12, 12, 23, 8, 34, 54, 7, 4]	j=1
21	Compare	2	7	-1	[1, 12, 12, 12, 23, 8, 34, 54, 7, 4]	j < gap, insert 3 at arr[1]
22	Insert	2	7	1	[1, 3, 12, 8, 23, 8, 34, 54, 7, 4]	Insert 3 at arr[1]
23	Next i	2	8	8	[1, 3, 12, 8, 23, 8, 34, 54, 7, 4]	temp=7, arr[6]=34 > 7, shift arr[6] to arr[8]
24	Shift	2	8	6	[1, 3, 12, 8, 23, 8, 34, 54, 34, 4]	j=6
25	Compare	2	8	4	[1, 3, 12, 8, 23, 8, 34, 54, 34, 4]	arr[4]=23 > 7, shift arr[4] to arr[6]
26	Shift	2	8	4	[1, 3, 12, 8, 23, 8, 23, 54, 34, 4]	j=4
27	Compare	2	8	2	[1, 3, 12, 8, 23, 8, 23, 54, 34, 4]	arr[2]=12 > 7, shift arr[2] to arr[4]
28	Shift	2	8	2	[1, 3, 12, 8, 12, 8, 23, 54, 34, 4]	j=2
29	Compare	2	8	0	[1, 3, 12, 8, 12, 8, 23, 54, 34, 4]	arr[0]=1 > 7? No, insert 7 at arr[2]
30	Insert	2	8	2	[1, 3, 7, 8, 12, 8, 23, 54, 34, 4]	Insert 7 at arr[2]
31	Next i	2	9	9	[1, 3, 7, 8, 12, 8, 23, 54, 34, 4]	temp=4, arr[7]=54 > 4, shift arr[7] to arr[9]
32	Shift	2	9	7	[1, 3, 7, 8, 12, 8, 23, 54, 34, 54]	j=7
33	Compare	2	9	5	[1, 3, 7, 8, 12, 8, 23, 54, 34, 54]	arr[5]=8 > 4, shift arr[5] to arr[7]
34	Shift	2	9	5	[1, 3, 7, 8, 12, 8, 23, 8, 34, 54]	j=5
35	Compare	2	9	3	[1, 3, 7, 8, 12, 8, 23, 8, 34, 54]	arr[3]=8 > 4, shift arr[3] to arr[5]
36	Shift	2	9	3	[1, 3, 7, 8, 12, 8, 23, 8, 34, 54]	j=3
37	Compare	2	9	1	[1, 3, 7, 8, 12, 8, 23, 8, 34, 54]	arr[1]=3 > 4? No, insert 4 at arr[3]
38	Insert	2	9	3	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	Insert 4 at arr[3]
39	Reduce gap	2/2=1	-	-	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	Set gap=1
40	Outer loop start	1	1	-	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	Start i=1
41	Compare arr[j-gap] and temp	1	1	1	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	temp=3, arr[0]=1 > 3? No, insert 3 at arr[1]
42	Next i	1	2	2	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	temp=7, arr[1]=3 > 7? No, insert 7 at arr[2]
43	Next i	1	3	3	[1, 3, 7, 4, 12, 8, 23, 8, 34, 54]	temp=4, arr[2]=7 > 4, shift arr[2] to arr[3]
44	Shift	1	3	2	[1, 3, 7, 7, 12, 8, 23, 8, 34, 54]	j=2
45	Compare	1	3	1	[1, 3, 7, 7, 12, 8, 23, 8, 34, 54]	arr[1]=3 > 4? No, insert 4 at arr[2]
46	Insert	1	3	2	[1, 3, 4, 7, 12, 8, 23, 8, 34, 54]	Insert 4 at arr[2]
47	Next i	1	4	4	[1, 3, 4, 7, 12, 8, 23, 8, 34, 54]	temp=12, arr[3]=7 > 12? No, insert 12 at arr[4]
48	Next i	1	5	5	[1, 3, 4, 7, 12, 8, 23, 8, 34, 54]	temp=8, arr[4]=12 > 8, shift arr[4] to arr[5]
49	Shift	1	5	4	[1, 3, 4, 7, 12, 12, 23, 8, 34, 54]	j=4
50	Compare	1	5	3	[1, 3, 4, 7, 12, 12, 23, 8, 34, 54]	arr[3]=7 > 8? No, insert 8 at arr[4]
51	Insert	1	5	4	[1, 3, 4, 7, 8, 12, 23, 8, 34, 54]	Insert 8 at arr[4]
52	Next i	1	6	6	[1, 3, 4, 7, 8, 12, 23, 8, 34, 54]	temp=23, arr[5]=12 > 23? No, insert 23 at arr[6]
53	Next i	1	7	7	[1, 3, 4, 7, 8, 12, 23, 8, 34, 54]	temp=8, arr[6]=23 > 8, shift arr[6] to arr[7]
54	Shift	1	7	6	[1, 3, 4, 7, 8, 12, 23, 23, 34, 54]	j=6
55	Compare	1	7	5	[1, 3, 4, 7, 8, 12, 23, 23, 34, 54]	arr[5]=12 > 8, shift arr[5] to arr[6]
56	Shift	1	7	5	[1, 3, 4, 7, 8, 12, 12, 23, 34, 54]	j=5
57	Compare	1	7	4	[1, 3, 4, 7, 8, 12, 12, 23, 34, 54]	arr[4]=8 > 8? No, insert 8 at arr[5]
58	Insert	1	7	5	[1, 3, 4, 7, 8, 8, 12, 23, 34, 54]	Insert 8 at arr[5]
59	Next i	1	8	8	[1, 3, 4, 7, 8, 8, 12, 23, 34, 54]	temp=34, arr[7]=23 > 34? No, insert 34 at arr[8]
60	Next i	1	9	9	[1, 3, 4, 7, 8, 8, 12, 23, 34, 54]	temp=54, arr[8]=34 > 54? No, insert 54 at arr[9]
61	Reduce gap	1/2=0	-	-	[1, 3, 4, 7, 8, 8, 12, 23, 34, 54]	gap=0, sorting done

💡 gap becomes 0, sorting is complete

Variable Tracker

Variable	Start	After Step 5	After Step 14	After Step 22	After Step 30	After Step 38	After Step 39	After Step 61
gap	5/2=2	2	2	2	2	2	1	0
i	-	2	6	7	8	9	9	-
j	-	0	2	1	2	3	3	-
array	[23,12,1,8,34,54,2,3,7,4]	[1,12,23,8,34,54,2,3,7,4]	[1,12,2,8,23,54,34,3,7,4]	[1,3,12,8,23,54,34,54,7,4]	[1,3,7,8,12,8,23,54,34,4]	[1,3,7,4,12,8,23,54,34,54]	[1,3,4,7,8,8,12,23,34,54]	[1,3,4,7,8,8,12,23,34,54]

Key Moments - 3 Insights

Why do we reduce the gap by half each time instead of decreasing by 1?

Reducing gap by half quickly narrows the distance between compared elements, efficiently moving elements closer to their final position. Decreasing by 1 would be slower and less efficient. See execution_table steps 1, 39, and 61 where gap changes from 2 to 1 to 0.

Why do we use a while loop inside the for loop to shift elements?

The while loop shifts elements that are greater than the temp value to the right, making space to insert temp in the correct position for the current gap. This is shown in execution_table steps 3-5 and 9-14.

What happens when gap becomes 1?

When gap is 1, the algorithm performs a normal insertion sort on the nearly sorted array, finalizing the order. This is shown in execution_table steps 39 to 61.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the array state?

A [1, 12, 23, 8, 34, 54, 2, 3, 7, 4]

B [23, 12, 1, 8, 34, 54, 2, 3, 7, 4]

C [23, 12, 23, 8, 34, 54, 2, 3, 7, 4]

D [1, 12, 1, 8, 34, 54, 2, 3, 7, 4]

💡 Hint

Check the 'Array State' column at step 5 in execution_table.

At which step does the gap reduce from 2 to 1?

A Step 38

B Step 39

C Step 22

D Step 61

💡 Hint

Look for 'Reduce gap' operation in execution_table.

According to variable_tracker, what is the value of 'gap' after step 39?

A 2

B 0

C 1

D 5

💡 Hint

Check the 'gap' row in variable_tracker after step 39.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Perform gapped insertion sort for each gap
- Reduce gap by half each iteration
- Finish when gap = 0
- Efficiently sorts by moving elements far apart first

Full Transcript

Shell Sort sorts an array by starting with a large gap between elements and sorting those elements. The gap is initially half the array size. For each gap, it performs a gapped insertion sort, shifting elements to their correct position within the gap. After completing for one gap, the gap is reduced by half, and the process repeats. When the gap reaches 1, it performs a normal insertion sort on the nearly sorted array, completing the sort. This method helps move elements closer to their final position faster than simple insertion sort. The execution table shows each step, including shifting and inserting elements, and how the array changes. The variable tracker shows how gap, i, j, and the array evolve. Key moments clarify why gap reduces by half, why shifting happens, and what occurs at gap 1. The visual quiz tests understanding of array states and gap changes during execution.

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