Shell Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

For each gap

↓

Perform gapped insertion sort

↓

Reduce gap (gap = gap/2)

↓

Repeat until gap = 0

↓

Array sorted

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap and sorts again, repeating until gap is 0 and array is sorted.

Execution Sample

DSA C++

void shellSort(int arr[], int n) {
  for (int gap = n/2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i++) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

This code sorts an array using Shell Sort by repeatedly sorting elements at a certain gap and reducing the gap until the array is sorted.

Execution Table

Step	Operation	Gap	Index i	Compare arr[j-gap] and temp	Swap/Shift	Array State
1	Initialize gap	5	-	-	-	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]
2	Start i loop	5	5	arr[0]=23 > temp=54? No	No shift	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]
3	i=6	5	6	arr[1]=12 > temp=2? Yes	Shift arr[6]=arr[1]=12	[23, 12, 1, 8, 34, 54, 12, 3, 7, 4]
4	i=6	5	1	No more shift	Place temp=2 at arr[1]	[23, 2, 1, 8, 34, 54, 12, 3, 7, 4]
5	i=7	5	7	arr[2]=1 > temp=3? No	No shift	[23, 2, 1, 8, 34, 54, 12, 3, 7, 4]
6	i=8	5	8	arr[3]=8 > temp=7? Yes	Shift arr[8]=arr[3]=8	[23, 2, 1, 8, 34, 54, 12, 3, 8, 4]
7	i=8	5	3	No more shift	Place temp=7 at arr[3]	[23, 2, 1, 7, 34, 54, 12, 3, 8, 4]
8	i=9	5	9	arr[4]=34 > temp=4? Yes	Shift arr[9]=arr[4]=34	[23, 2, 1, 7, 34, 54, 12, 3, 8, 34]
9	i=9	5	4	No more shift	Place temp=4 at arr[4]	[23, 2, 1, 7, 4, 54, 12, 3, 8, 34]
10	Reduce gap	2	-	-	-	[23, 2, 1, 7, 4, 54, 12, 3, 8, 34]
11	i=2	2	2	arr[0]=23 > temp=1? Yes	Shift arr[2]=arr[0]=23	[23, 2, 23, 7, 4, 54, 12, 3, 8, 34]
12	i=2	2	0	No more shift	Place temp=1 at arr[0]	[1, 2, 23, 7, 4, 54, 12, 3, 8, 34]
13	i=3	2	3	arr[1]=2 > temp=7? No	No shift	[1, 2, 23, 7, 4, 54, 12, 3, 8, 34]
14	i=4	2	4	arr[2]=23 > temp=4? Yes	Shift arr[4]=arr[2]=23	[1, 2, 23, 7, 23, 54, 12, 3, 8, 34]
15	i=4	2	2	arr[0]=1 > temp=4? No	Place temp=4 at arr[2]	[1, 2, 4, 7, 23, 54, 12, 3, 8, 34]
16	i=5	2	5	arr[3]=7 > temp=54? No	No shift	[1, 2, 4, 7, 23, 54, 12, 3, 8, 34]
17	i=6	2	6	arr[4]=23 > temp=12? Yes	Shift arr[6]=arr[4]=23	[1, 2, 4, 7, 23, 54, 23, 3, 8, 34]
18	i=6	2	4	arr[2]=4 > temp=12? No	Place temp=12 at arr[4]	[1, 2, 4, 7, 12, 54, 23, 3, 8, 34]
19	i=7	2	7	arr[5]=54 > temp=3? Yes	Shift arr[7]=arr[5]=54	[1, 2, 4, 7, 12, 54, 23, 54, 8, 34]
20	i=7	2	5	arr[3]=7 > temp=3? Yes	Shift arr[5]=arr[3]=7	[1, 2, 4, 7, 12, 7, 23, 54, 8, 34]
21	i=7	2	3	arr[1]=2 > temp=3? No	Place temp=3 at arr[3]	[1, 2, 4, 3, 12, 7, 23, 54, 8, 34]
22	i=8	2	8	arr[6]=23 > temp=8? Yes	Shift arr[8]=arr[6]=23	[1, 2, 4, 3, 12, 7, 23, 54, 23, 34]
23	i=8	2	6	arr[4]=12 > temp=8? Yes	Shift arr[6]=arr[4]=12	[1, 2, 4, 3, 12, 7, 12, 54, 23, 34]
24	i=8	2	4	arr[2]=4 > temp=8? No	Place temp=8 at arr[4]	[1, 2, 4, 3, 8, 7, 12, 54, 23, 34]
25	i=9	2	9	arr[7]=54 > temp=34? Yes	Shift arr[9]=arr[7]=54	[1, 2, 4, 3, 8, 7, 12, 54, 23, 54]
26	i=9	2	7	arr[5]=7 > temp=34? No	Place temp=34 at arr[7]	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
27	Reduce gap	1	-	-	-	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
28	i=1	1	1	arr[0]=1 > temp=2? No	No shift	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
29	i=2	1	2	arr[1]=2 > temp=4? No	No shift	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
30	i=3	1	3	arr[2]=4 > temp=3? Yes	Shift arr[3]=arr[2]=4	[1, 2, 4, 4, 8, 7, 12, 34, 23, 54]
31	i=3	1	2	arr[1]=2 > temp=3? No	Place temp=3 at arr[2]	[1, 2, 3, 4, 8, 7, 12, 34, 23, 54]
32	i=4	1	4	arr[3]=4 > temp=8? No	No shift	[1, 2, 3, 4, 8, 7, 12, 34, 23, 54]
33	i=5	1	5	arr[4]=8 > temp=7? Yes	Shift arr[5]=arr[4]=8	[1, 2, 3, 4, 8, 8, 12, 34, 23, 54]
34	i=5	1	4	arr[3]=4 > temp=7? No	Place temp=7 at arr[4]	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
35	i=6	1	6	arr[5]=8 > temp=12? No	No shift	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
36	i=7	1	7	arr[6]=12 > temp=34? No	No shift	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
37	i=8	1	8	arr[7]=34 > temp=23? Yes	Shift arr[8]=arr[7]=34	[1, 2, 3, 4, 7, 8, 12, 34, 34, 54]
38	i=8	1	7	arr[6]=12 > temp=23? No	Place temp=23 at arr[7]	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]
39	i=9	1	9	arr[8]=34 > temp=54? No	No shift	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]
40	Reduce gap	0	-	-	-	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]

💡 Gap reduced to 0, sorting complete

Variable Tracker

Variable	Start	After gap=5	After gap=2	After gap=1	Final
gap	N/A	5	2	1	0
i	N/A	5 to 9	2 to 9	1 to 9	N/A
Array State	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]	[23, 2, 1, 7, 4, 54, 12, 3, 8, 34]	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]

Key Moments - 3 Insights

Why do we start with a large gap and reduce it instead of sorting normally?

Starting with a large gap moves elements far apart closer to their correct positions quickly, reducing the total number of shifts needed later. This is shown in execution_table rows 1-9 where gap=5 sorts distant elements first.

Why do we use a gapped insertion sort inside the loop?

The gapped insertion sort compares and shifts elements that are gap distance apart, sorting sublists. This is visible in rows 11-26 where elements are shifted by gap=2, not adjacent positions.

When does the sorting finish?

Sorting finishes when gap reduces to 0 (row 40), meaning the array is fully sorted with gap=1 insertion sort completed.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the array state after placing temp=2?

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

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

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

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

💡 Hint

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

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

A Step 10

B Step 11

C Step 9

D Step 27

💡 Hint

Look for 'Reduce gap' operation in execution_table

If the initial gap was set to n/3 instead of n/2, how would the execution_table change?

A The gap would never reduce to zero

B The array would be sorted immediately without any shifts

C The gap values in the table would start smaller, changing the steps and array states accordingly

D The array state would remain unchanged throughout

💡 Hint

Consider how gap initialization affects the sorting passes shown in execution_table

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Perform gapped insertion sort for each gap
- Reduce gap by half each iteration
- Repeat until gap = 0
- Efficiently moves elements closer to sorted position
- Final pass with gap=1 completes sorting

Full Transcript

Shell Sort sorts an array by starting with a large gap between elements and sorting those elements. Then it reduces the gap and sorts again. This repeats until the gap is zero, meaning the array is fully sorted. The code uses a loop for gap starting at n/2, then a nested loop for insertion sort with that gap. Elements are compared and shifted if needed. The execution table shows each step, the gap, the index, comparisons, shifts, and the array state. Key moments include why large gaps help, how gapped insertion sort works, and when sorting finishes. The visual quiz tests understanding of array states and gap changes. The snapshot summarizes the algorithm steps clearly.

Practice

1. What is the main idea behind the Shell Sort algorithm?

easy

A. It sorts elements by building a binary heap.

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

Solution

1. Step 1: Understand Shell Sort's approach

   Shell Sort starts by comparing elements far apart using a gap, not just neighbors.

2. Step 2: Gap reduction and sorting

   The gap reduces gradually until it becomes 1, performing insertion sort at each stage.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based sorting [OK]

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

Common Mistakes:

• Thinking Shell Sort only swaps adjacent elements
• Confusing Shell Sort with merge or heap sort
• Ignoring the gap reduction step

2. Which of the following is the correct way to initialize the gap in Shell Sort for an array of size n in C++?

easy

A. int gap = n / 2;

B. int gap = n * 2;

C. int gap = n + 1;

D. int gap = 1;

Solution

1. Step 1: Identify the common gap initialization

   Shell Sort commonly starts with gap as half the array size, i.e., n/2.

2. Step 2: Check other options

   Multiplying or adding to n is incorrect; starting at 1 skips the gap sorting steps.

3. Final Answer:

   int gap = n / 2; -> Option A

4. Quick Check:

   Gap starts at half array size [OK]

Hint: Gap usually starts at half the array length [OK]

Common Mistakes:

• Starting gap at 1 instead of n/2
• Using gap larger than array size
• Confusing gap initialization with loop counters

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

medium

A. [1, 3, 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. [3, 1, 4, 5, 6, 7, 8, 9]

Solution

1. Step 1: Apply Shell Sort steps on the array

   Start with gap = 4 (8/2), sort elements 4 apart, then gap = 2, then gap = 1.

2. Step 2: Final sorted array

   After all gap reductions and sorting, 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 A

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

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

Common Mistakes:

• Confusing partial sorted arrays as final output
• Reversing the array order
• Ignoring gap-based sorting steps

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

void shellSort(int arr[], int n) {
  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;
    }
  }
}

medium

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

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

C. The gap should start from n, not n/2.

D. The gap update should be gap = gap - 1 instead of gap /= 2.

Solution

1. Step 1: Review gap initialization and update

   Gap starts at n/2 and halves each iteration, which is correct for Shell Sort.

2. Step 2: Check inner loop and conditions

   The while loop uses j >= gap to avoid out-of-bound and correctly shifts elements.

3. Final Answer:

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

4. Quick Check:

   Code matches Shell Sort logic [OK]

Hint: Check gap halving and while loop conditions carefully [OK]

Common Mistakes:

• Changing gap update to subtract 1 breaks algorithm
• Using incorrect while loop boundary causes errors
• Starting gap at n causes out-of-bound issues

5. Given an array arr = {23, 12, 1, 8, 34, 54, 2, 3}, how many times will the inner while loop execute during the first gap iteration (gap = 4) in Shell Sort?

hard

A. 5 times

B. 4 times

C. 3 times

D. 6 times

Solution

1. Step 1: Identify elements compared with gap = 4

   Pairs compared: (23, 34), (12, 54), (1, 2), (8, 3).

2. Step 2: Count while loop executions

   Only pairs where left element > right element cause shifts. Here, (23 > 34) no, (12 > 54) no, (1 > 2) no, (8 > 3) yes. For (8,3), shifting occurs once. Also, elements at indices 4 to 7 are checked, total 4 iterations of the outer loop, but only 1 inner while loop execution occurs.

3. Final Answer:

   3 times -> Option C

4. Quick Check:

   Count actual inner while loop executions, not just comparisons [OK]

Hint: Count pairs separated by gap and check conditions [OK]

Common Mistakes:

• Counting only swaps, not all while loop checks
• Ignoring elements beyond first gap iteration
• Misunderstanding gap-based comparisons