Shell Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array and initial gap

↓

For each gap: gap = gap / 2

↓

For each element from gap to end

↓

Compare element with elements gap apart

↓

Shift elements if needed

↓

Insert element at correct position

↓

Repeat until gap = 0

↓

Sorted array

Shell Sort starts with a large gap and reduces it, sorting elements far apart, then closer, until fully sorted.

Execution Sample

DSA C#

int[] arr = {5, 3, 8, 1, 2};
int n = arr.Length;
for (int gap = n / 2; gap > 0; gap /= 2) {
  for (int i = gap; i < n; i++) {
    int temp = arr[i];
    int j = i;
    while (j >= gap && arr[j - gap] > temp) {
      arr[j] = arr[j - gap];
      j -= gap;
    }
    arr[j] = temp;
  }
}

This code sorts the array using Shell Sort by reducing gap and inserting elements in correct positions. For example, {5,3,8,1,2} becomes {1,2,3,5,8}.

Execution Table

Step	Operation	Gap	Index i	Compare Indices	Swap/Shift	Array State
1	Initialize gap	2	-	-	-	[5, 3, 8, 1, 2]
2	i=2, temp=8	2	2	arr[0]=5 > 8? No	No shift	[5, 3, 8, 1, 2]
3	i=3, temp=1	2	3	arr[1]=3 > 1	Shift arr[3] <- arr[1]	[5, 3, 8, 3, 2]
4	j=1 < 2, insert	2	3	-	Insert temp=1 at arr[1]	[5, 1, 8, 3, 2]
5	i=4, temp=2	2	4	arr[2]=8 > 2	Shift arr[4] <- arr[2]	[5, 1, 8, 3, 8]
6	j=2	2	4	arr[0]=5 > 2	Shift arr[2] <- arr[0]	[5, 1, 5, 3, 8]
7	j=0 < 2, insert	2	4	-	Insert temp=2 at arr[0]	[2, 1, 5, 3, 8]
8	Update gap	1	-	-	-	[2, 1, 5, 3, 8]
9	i=1, temp=1	1	1	arr[0]=2 > 1	Shift arr[1] <- arr[0]	[2, 2, 5, 3, 8]
10	j=0 < 1, insert	1	1	-	Insert temp=1 at arr[0]	[1, 2, 5, 3, 8]
11	i=2, temp=5	1	2	arr[1]=2 > 5? No	No shift	[1, 2, 5, 3, 8]
12	i=3, temp=3	1	3	arr[2]=5 > 3	Shift arr[3] <- arr[2]	[1, 2, 5, 5, 8]
13	j=2	1	3	arr[1]=2 > 3? No	Insert temp=3 at arr[2]	[1, 2, 3, 5, 8]
14	i=4, temp=8	1	4	arr[3]=5 > 8? No	No shift	[1, 2, 3, 5, 8]
15	gap=0, done	0	-	-	-	[1, 2, 3, 5, 8]

💡 Gap reduced to 0, array is fully sorted.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	After Step 11	After Step 13	Final
gap	2	2	2	1	1	1	0
i	-	3	4	1	2	3	-
temp	-	1	2	1	5	3	-
array	[5, 3, 8, 1, 2]	[5, 1, 8, 3, 2]	[2, 1, 5, 3, 8]	[1, 2, 5, 3, 8]	[1, 2, 5, 3, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we start comparing elements that are 'gap' apart instead of adjacent?

Shell Sort compares elements 'gap' apart to move elements faster towards their correct position, reducing disorder more quickly than simple adjacent swaps. See steps 3-7 where gap=2 allows shifting elements separated by 2 indices.

Why do we reduce the gap by dividing it by 2 each time?

Reducing gap by half each time gradually refines the sorting from coarse to fine. Larger gaps move elements far apart, smaller gaps finalize the order. This is shown in step 8 where gap changes from 2 to 1.

What happens when gap becomes 1?

When gap is 1, Shell Sort performs a normal insertion sort to finalize sorting. This is shown in steps 9-14 where elements are shifted and inserted one by one.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 7?

A [1, 2, 3, 5, 8]

B [5, 3, 8, 1, 2]

C [2, 1, 5, 3, 8]

D [5, 1, 8, 3, 2]

💡 Hint

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

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

A Step 1

B Step 8

C Step 15

D Step 7

💡 Hint

Look at the 'Gap' column in the execution_table to find when gap changes from 2 to 1.

If the initial array was already sorted, how would the 'Swap/Shift' column change in the first gap iteration?

A All would be 'No shift'

B All would be 'Shift arr[...]'

C Some would be 'Shift', some 'No shift'

D No operations would happen

💡 Hint

Refer to steps 2, 11, 14 where no shifts happen when elements are in order.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Compare and shift elements gap apart
- Reduce gap by half each iteration
- Finish with gap = 1 (insertion sort)
- Efficient for medium-sized arrays
- Moves elements faster than simple insertion sort

Full Transcript

Shell Sort is a sorting method that starts by comparing elements far apart using a gap value. The gap begins at half the array size and reduces by half each time. For each gap, elements are compared and shifted if needed to move them closer to their correct position. When the gap reaches 1, the algorithm performs a final insertion sort to complete sorting. This approach helps move elements faster than simple insertion sort, improving efficiency. The execution table shows each step, including gap changes, comparisons, shifts, and the array state after each operation.

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 comparing distant elements and gradually reducing the gap.

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

D. It sorts elements by inserting each element into its correct position one by one.

Solution

1. Step 1: Understand Shell Sort concept

   Shell Sort improves insertion sort by comparing elements far apart, not just neighbors.

2. Step 2: Identify the gap reduction process

   The algorithm starts with a large gap and reduces it until it becomes 1, sorting partially at each step.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based sorting [OK]

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

Common Mistakes:

• Confusing Shell Sort with Bubble Sort
• Thinking it only swaps adjacent elements
• Mixing it up with Merge Sort or Quick Sort

2. Which of the following is the correct way to declare the initial gap in Shell Sort in C#?

easy

A. int gap = array.Length + 1;

B. int gap = array.Length * 2;

C. int gap = 1;

D. int gap = array.Length / 2;

Solution

1. Step 1: Recall Shell Sort gap initialization

   The initial gap is usually half the length of the array to start comparing distant elements.

2. Step 2: Check each option

   Only int gap = array.Length / 2; correctly sets gap to half the array length.

3. Final Answer:

   int gap = array.Length / 2; -> Option D

4. Quick Check:

   Initial gap = half array length [OK]

Hint: Start gap at half array size for Shell Sort [OK]

Common Mistakes:

• Setting gap larger than array length
• Starting gap at 1 instead of half length
• Using multiplication instead of division

3. What will be the output array after applying Shell Sort on int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};?

medium

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

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

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

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

Solution

1. Step 1: Understand Shell Sort process on given array

   Shell Sort will sort the array by reducing gaps and partially sorting until fully sorted.

2. Step 2: Trace sorting steps mentally

   After full Shell Sort, the array becomes fully sorted in ascending order: [1, 3, 4, 5, 6, 7, 8, 9].

3. Final Answer:

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

4. Quick Check:

   Shell Sort output = sorted array ascending [OK]

Hint: Shell Sort outputs fully sorted array ascending [OK]

Common Mistakes:

• Confusing partial sorted arrays as final output
• Reversing the order by mistake
• Ignoring gap reduction steps

4. Identify the error in this Shell Sort code snippet:

int gap = arr.Length / 2;
while (gap > 0) {
  for (int i = gap; i < arr.Length; i++) {
    int temp = arr[i];
    int j = i;
    while (j >= gap && arr[j - gap] > temp) {
      arr[j] = arr[j - gap];
      j -= gap;
    }
    arr[j] = temp;
  }
  gap = gap / 2;
}

medium

A. The gap update should be gap = gap / 2, which is correct here.

B. The inner while condition should be j > gap, not j >= gap.

C. The initial gap should be arr.Length, not arr.Length / 2.

D. The gap update should be gap = gap / 3, not gap / 2.

Solution

1. Step 1: Review gap update logic

   The gap is correctly initialized as half the array length and updated by dividing by 2 each iteration.

2. Step 2: Check inner loop conditions

   The inner while loop condition j >= gap is correct to avoid index out of bounds and compare elements properly.

3. Final Answer:

   The gap update should be gap = gap / 2, which is correct here. -> Option A

4. Quick Check:

   Gap update = gap / 2 is correct [OK]

Hint: Gap halves each iteration; inner loop uses j >= gap [OK]

Common Mistakes:

• Changing gap update to incorrect divisor
• Using wrong inner loop condition causing errors
• Initializing gap incorrectly

5. You want to optimize Shell Sort for a large array by choosing a better gap sequence. Which of these sequences is known to improve performance over simple halving?

hard

A. Using gaps from the sequence: 1, 4, 13, 40, 121, 364, 1093 (Knuth's sequence)

B. Using gaps as powers of two: 16, 8, 4, 2, 1

C. Using gaps as prime numbers only: 7, 5, 3, 2, 1

D. Using gaps as random numbers less than array length

Solution

1. Step 1: Understand gap sequences in Shell Sort

   Different gap sequences affect Shell Sort's efficiency; Knuth's sequence is a well-known optimized choice.

2. Step 2: Identify the known efficient sequence

   Knuth's sequence (1, 4, 13, 40, 121, 364, 1093) improves performance compared to simple halving.

3. Final Answer:

   Using gaps from the sequence: 1, 4, 13, 40, 121, 364, 1093 (Knuth's sequence) -> Option A

4. Quick Check:

   Knuth's gap sequence = better Shell Sort performance [OK]

Hint: Use Knuth's gap sequence for faster Shell Sort [OK]

Common Mistakes:

• Using random gaps causing poor sorting
• Assuming powers of two are always best
• Ignoring known optimized sequences