Shell Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

For gap > 0

↓

For i = gap to end

↓

Compare and shift elements gap apart

↓

Insert element in correct position

↓

Reduce gap (gap = gap/2)

↓

Repeat until gap = 0

↓

Sorted array ready

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap until it sorts the whole array.

Execution Sample

DSA Java

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 comparing elements at a gap and reducing the gap each pass.

Execution Table

Step	Operation	Gap	Index i	Compared Indices	Swap/Shift	Array State
1	Initialize gap	2	-	-	-	[5, 3, 8, 1, 2]
2	i=2, temp=8	2	2	0 and 2 (5 and 8)	No shift	[5, 3, 8, 1, 2]
3	i=3, temp=1	2	3	1 and 3 (3 and 1)	Shift 3 to index 3	[5, 3, 8, 3, 2]
4	Insert temp=1 at index 1	2	1	-	-	[5, 1, 8, 3, 2]
5	i=4, temp=2	2	4	2 and 4 (8 and 2)	Shift 8 to index 4	[5, 1, 8, 3, 8]
6	i=4 continued: shift 5 to 2 then insert at 0	2	4	0 and 2 (5 and 2)	Shift 5 to index 2, insert temp=2	[2, 1, 5, 3, 8]
7	Reduce gap	1	-	-	-	[2, 1, 5, 3, 8]
8	i=1, temp=1	1	1	0 and 1 (2 and 1)	Shift 2 to index 1	[2, 2, 5, 3, 8]
9	Insert temp=1 at index 0	1	0	-	-	[1, 2, 5, 3, 8]
10	i=2, temp=5	1	2	1 and 2 (2 and 5)	No shift	[1, 2, 5, 3, 8]
11	Insert temp=5 at index 2	1	2	-	-	[1, 2, 5, 3, 8]
12	i=3, temp=3	1	3	2 and 3 (5 and 3)	Shift 5 to index 3	[1, 2, 5, 5, 8]
13	Insert temp=3 at index 2	1	2	-	-	[1, 2, 3, 5, 8]
14	i=4, temp=8	1	4	3 and 4 (5 and 8)	No shift	[1, 2, 3, 5, 8]
15	Reduce gap	0	-	-	-	[1, 2, 3, 5, 8]

💡 Gap reduced to 0, sorting complete.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 11	After Step 13	Final
gap	2	2	2	2	1	1	1	0
i	-	2	3	4	1	2	3	-
temp	-	8	1	2	1	5	3	-
array	[5, 3, 8, 1, 2]	[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 with a gap of n/2 instead of 1?

Starting with a larger gap allows the algorithm to move elements far apart closer to their correct positions early, reducing the total number of shifts later. This is shown in the execution_table steps 1-6 where gap=2 helps partially sort the array before gap=1.

Why do we shift elements instead of swapping directly?

Shifting elements creates space for the temp value to be inserted in the correct position without multiple swaps. This is visible in steps 3, 5, 6, 8, and 12 where elements are shifted right to insert temp.

When does the sorting finish?

Sorting finishes when gap reduces to 0, as shown in step 15. At this point, the array is fully sorted.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

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

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

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look for the 'Reduce gap' operation and gap value change in the execution_table.

If the initial gap was set to 1, how would the first pass in the execution_table change?

A The array would be sorted immediately

B There would be no shifts

C It would be the same as step 8 onwards

D The gap would never reduce

💡 Hint

Compare the operations when gap=1 in steps 8-14 with the initial pass.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Compare and shift elements gap apart
- Insert element in correct position
- Reduce gap by half each pass
- Repeat until gap = 0
- Array becomes sorted progressively

Full Transcript

Shell Sort sorts an array by starting with a large gap between elements and sorting those elements. The gap starts at half the array length and reduces by half each time. For each gap, the algorithm compares elements that are gap apart and shifts larger elements to the right to insert the current element in the correct position. This process repeats until the gap becomes zero, meaning the array is fully sorted. The execution table shows each step, including the gap, indices compared, shifts, and the array state after each operation. Key moments include why the gap starts at n/2, why shifting is used instead of swapping, and when the sorting finishes. The visual quiz tests understanding of array states and gap changes during the sort.

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 to sort subarrays independently.

D. It builds a sorted list by inserting elements one by one in order.

Solution

1. Step 1: Understand Shell Sort concept

   Shell Sort improves insertion sort by comparing elements far apart, reducing the gap over iterations.

2. Step 2: Compare options with concept

   It sorts elements by comparing distant elements and gradually reducing the gap. correctly describes this gap reduction and distant element comparison. Others describe different sorting methods.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap reduction and distant comparisons [OK]

Hint: Shell Sort uses gaps to compare distant elements first [OK]

Common Mistakes:

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

2. Which of the following is the correct way to initialize the gap variable in Shell Sort in Java?

easy

A. int gap = arr.length / 2;

B. int gap = arr.length * 2;

C. int gap = arr.length + 1;

D. int gap = 0;

Solution

1. Step 1: Understand gap initialization

   Shell Sort starts with a gap usually half the array length to compare distant elements.

2. Step 2: Check options for correct initialization

   int gap = arr.length / 2; correctly sets gap to half the array length. Others are incorrect or ineffective.

3. Final Answer:

   int gap = arr.length / 2; -> Option A

4. Quick Check:

   Gap starts at half array length [OK]

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

Common Mistakes:

• Setting gap larger than array length
• Starting gap at zero causing no sorting
• Using gap as array length plus one

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

medium

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

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

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

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

Solution

1. Step 1: Apply Shell Sort on given array

   Start with gap = 4 (8/2), compare and swap distant elements, then reduce gap to 2, then 1, sorting progressively.

2. Step 2: Final sorted array

   After all gap reductions and swaps, the array becomes fully sorted: [1, 3, 4, 5, 6, 7, 8, 9].

3. Final Answer:

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

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

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

Common Mistakes:

• Confusing partial sorted states as final output
• Ignoring gap reductions
• Assuming reverse order output

4. Identify the error in this Shell Sort snippet:

for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  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;
  }
}

medium

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

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

C. No error; the code correctly implements Shell Sort.

D. The variable temp should be declared outside the loops.

Solution

1. Step 1: Analyze the loop and conditions

   The gap starts at half array length and halves each iteration, which is a common Shell Sort approach.

2. Step 2: Check inner loop and assignments

   The inner while loop correctly shifts elements greater than temp, and temp is assigned properly after shifting.

3. Final Answer:

   No error; the code correctly implements Shell Sort. -> Option C

4. Quick Check:

   Code matches standard Shell Sort logic [OK]

Hint: Check loop conditions and assignments carefully [OK]

Common Mistakes:

• Changing gap update incorrectly
• Misusing loop conditions causing index errors
• Declaring variables in wrong scope

5. Given an array int[] arr = {20, 35, -15, 7, 55, 1, -22};, how many times will the inner while loop execute during the first gap iteration in Shell Sort?

hard

A. 5 times

B. 3 times

C. 7 times

D. 9 times

Solution

1. Step 1: Determine initial gap

   Array length 7, gap = 3. Process i from 3 to 6.

2. Step 2: Count inner while loop executions (shifts)

   Initial: [20,35,-15,7,55,1,-22]
   - i=3, temp=7 vs arr[0]=20: 1 shift -> [7,35,-15,20,55,1,-22]
   - i=4, temp=55 vs arr[1]=35: 0 shifts (35 < 55)
   - i=5, temp=1 vs arr[2]=-15: 0 shifts (-15 < 1)
   - i=6, temp=-22 vs arr[3]=20 then arr[0]=7: 2 shifts
   Total: 1+0+0+2 = 3.

3. Final Answer:

   3 times -> Option B

4. Quick Check:

   Shifts first gap = 3 [OK]

Hint: Count shifts for each gap iteration carefully [OK]

Common Mistakes:

• Counting only comparisons, not shifts
• Ignoring multiple shifts per element
• Miscalculating gap or indices