Shell Sort Algorithm in DSA C - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose gap = n/2

↓

For each gap > 0

↓

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 until it sorts the whole array.

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 = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
}

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

Execution Table

Step	Operation	Gap	Index i	Compare Indices	Swap/Shift	Array State
1	Initialize gap	5	-	-	-	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]
2	i=5, temp=54	5	5	0 and 5 (23 vs 54)	No shift	[23, 12, 1, 8, 34, 54, 2, 3, 7, 4]
3	i=6, temp=2	5	6	1 and 6 (12 vs 2)	Shift 12 to index 6	[23, 12, 1, 8, 34, 54, 12, 3, 7, 4]
4	j=1, compare 12 and 2	5	6	No more shift	Place 2 at index 1	[23, 2, 1, 8, 34, 54, 12, 3, 7, 4]
5	i=7, temp=3	5	7	2 and 7 (1 vs 3)	No shift	[23, 2, 1, 8, 34, 54, 12, 3, 7, 4]
6	i=8, temp=7	5	8	3 and 8 (8 vs 7)	Shift 8 to index 8	[23, 2, 1, 8, 34, 54, 12, 3, 8, 4]
7	j=3, compare 8 and 7	5	8	No more shift	Place 7 at index 3	[23, 2, 1, 7, 34, 54, 12, 3, 8, 4]
8	i=9, temp=4	5	9	4 and 9 (34 vs 4)	Shift 34 to index 9	[23, 2, 1, 7, 34, 54, 12, 3, 8, 34]
9	j=4, compare 34 and 4	5	9	No more shift	Place 4 at index 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, temp=1	2	2	0 and 2 (23 vs 1)	Shift 23 to index 2	[23, 2, 23, 7, 4, 54, 12, 3, 8, 34]
12	j=0, compare 23 and 1	2	2	No more shift	Place 1 at index 0	[1, 2, 23, 7, 4, 54, 12, 3, 8, 34]
13	i=3, temp=7	2	3	1 and 3 (2 vs 7)	No shift	[1, 2, 23, 7, 4, 54, 12, 3, 8, 34]
14	i=4, temp=4	2	4	2 and 4 (23 vs 4)	Shift 23 to index 4	[1, 2, 23, 7, 23, 54, 12, 3, 8, 34]
15	j=2, compare 23 and 4	2	4	No more shift	Place 4 at index 2	[1, 2, 4, 7, 23, 54, 12, 3, 8, 34]
16	i=5, temp=54	2	5	3 and 5 (7 vs 54)	No shift	[1, 2, 4, 7, 23, 54, 12, 3, 8, 34]
17	i=6, temp=12	2	6	4 and 6 (23 vs 12)	Shift 23 to index 6	[1, 2, 4, 7, 23, 54, 23, 3, 8, 34]
18	j=4, compare 23 and 12	2	6	No more shift	Place 12 at index 4	[1, 2, 4, 7, 12, 54, 23, 3, 8, 34]
19	i=7, temp=3	2	7	5 and 7 (54 vs 3)	Shift 54 to index 7	[1, 2, 4, 7, 12, 54, 23, 54, 8, 34]
20	j=5, compare 54 and 3	2	7	3 and 5 (7 vs 3)	Shift 7 to index 5	[1, 2, 4, 7, 12, 7, 23, 54, 8, 34]
21	j=3, compare 7 and 3	2	7	No more shift	Place 3 at index 3	[1, 2, 4, 3, 12, 7, 23, 54, 8, 34]
22	i=8, temp=8	2	8	6 and 8 (23 vs 8)	Shift 23 to index 8	[1, 2, 4, 3, 12, 7, 23, 54, 23, 34]
23	j=6, compare 23 and 8	2	8	4 and 6 (12 vs 8)	Shift 12 to index 6	[1, 2, 4, 3, 12, 7, 12, 54, 23, 34]
24	j=4, compare 12 and 8	2	8	No more shift	Place 8 at index 4	[1, 2, 4, 3, 8, 7, 12, 54, 23, 34]
25	i=9, temp=34	2	9	7 and 9 (54 vs 34)	Shift 54 to index 9	[1, 2, 4, 3, 8, 7, 12, 54, 23, 54]
26	j=7, compare 54 and 34	2	9	No more shift	Place 34 at index 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, temp=2	1	1	0 and 1 (1 vs 2)	No shift	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
29	i=2, temp=4	1	2	1 and 2 (2 vs 4)	No shift	[1, 2, 4, 3, 8, 7, 12, 34, 23, 54]
30	i=3, temp=3	1	3	2 and 3 (4 vs 3)	Shift 4 to index 3	[1, 2, 4, 4, 8, 7, 12, 34, 23, 54]
31	j=2, compare 4 and 3	1	3	No more shift	Place 3 at index 2	[1, 2, 3, 4, 8, 7, 12, 34, 23, 54]
32	i=4, temp=8	1	4	3 and 4 (4 vs 8)	No shift	[1, 2, 3, 4, 8, 7, 12, 34, 23, 54]
33	i=5, temp=7	1	5	4 and 5 (8 vs 7)	Shift 8 to index 5	[1, 2, 3, 4, 8, 8, 12, 34, 23, 54]
34	j=4, compare 8 and 7	1	5	No more shift	Place 7 at index 4	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
35	i=6, temp=12	1	6	5 and 6 (8 vs 12)	No shift	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
36	i=7, temp=34	1	7	6 and 7 (12 vs 34)	No shift	[1, 2, 3, 4, 7, 8, 12, 34, 23, 54]
37	i=8, temp=23	1	8	7 and 8 (34 vs 23)	Shift 34 to index 8	[1, 2, 3, 4, 7, 8, 12, 34, 34, 54]
38	j=7, compare 34 and 23	1	8	No more shift	Place 23 at index 7	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]
39	i=9, temp=54	1	9	8 and 9 (34 vs 54)	No shift	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]
40	gap=0, done	0	-	-	-	[1, 2, 3, 4, 7, 8, 12, 23, 34, 54]

💡 Gap reduced to 0, array is fully sorted

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 10	After Step 15	After Step 27	Final
gap	5	5	5	2	2	1	0
i	-	5	6	2	4	1	9
j	-	5	1	0	2	2	8
temp	-	54	2	1	4	2	54
Array State	[23,12,1,8,34,54,2,3,7,4]	[23,12,1,8,34,54,12,3,7,4]	[23,2,1,7,4,54,12,3,8,34]	[1,2,4,7,12,54,23,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 the whole array at once?

Starting with a large gap moves elements far apart closer to their correct position quickly, reducing total shifts later. This is shown in steps 2-9 where large gaps move big elements, making later small-gap sorts faster.

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

The while loop shifts elements that are greater than temp to the right until the correct position for temp is found. This is visible in steps like 3-4 and 14-15 where multiple shifts happen before placing temp.

What happens when gap becomes 1?

When gap is 1, Shell Sort performs a normal insertion sort on the nearly sorted array, finalizing the order. Steps 27-39 show this final pass where small shifts finish sorting.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what happens to the array?

A Element 12 is shifted to index 6 and 2 is placed at index 1

B Element 2 is shifted to index 6 and 12 is placed at index 1

C No changes to the array

D Element 54 is swapped with 23

💡 Hint

Check the 'Swap/Shift' and 'Array State' columns at step 4 in the execution_table

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

A Step 9

B Step 10

C Step 15

D Step 27

💡 Hint

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

According to variable_tracker, what is the value of 'temp' after step 15?

A 4

B 12

C 1

D 7

💡 Hint

Check the 'temp' row and the column for 'After Step 15' in variable_tracker

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 is normal insertion sort

Full Transcript

Shell Sort sorts an array by starting with a large gap between compared elements. It performs insertion sort on elements that are gap distance apart. After each pass, the gap is reduced by half. This process repeats until the gap is zero, meaning the array is fully sorted. The algorithm moves elements far apart closer to their correct position early, reducing the total number of shifts needed later. The final pass with gap 1 is a normal insertion sort on a nearly sorted array, making it efficient. The execution table shows each step of shifting and placing elements, and the variable tracker shows how gap, indices, and temp change over time.

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 uses a divide and conquer approach like merge sort.

C. It builds a heap and extracts the maximum element repeatedly.

D. It repeatedly swaps adjacent elements if they are in wrong order.

Solution

1. Step 1: Understand Shell Sort concept

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

2. Step 2: Identify the gap reduction

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

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap comparison and reduction [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax to start the gap value in Shell Sort for an array of size n in C?

easy

A. int gap = n * 2;

B. int gap = n - 1;

C. int gap = n / 2;

D. int gap = 1;

Solution

1. Step 1: Identify typical initial gap

   Shell Sort usually starts with gap as half the array size, so gap = n / 2.

2. Step 2: Check other options

   Multiplying by 2 or using n-1 is not standard; starting at 1 is too small for initial gap.

3. Final Answer:

   int gap = n / 2; -> Option C

4. Quick Check:

   Initial gap = n/2 [OK]

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

Common Mistakes:

• Starting gap at 1 instead of n/2
• Using n*2 which is too large
• Using n-1 which is not standard

3. What will be the output array after applying one full pass of Shell Sort with initial gap = 3 on the array [9, 8, 3, 7, 5, 6, 4, 1]?

medium

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

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

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

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

Solution

1. Step 1: Identify elements compared with gap 3

   Elements compared are at indices (0,3,6), (1,4,7), and (2,5).

2. Step 2: Sort elements in these groups

   Group 1: [9,7,4] sorted -> [4, 8, 3, 1, 5, 6, 7, 9]

3. Step 3: Place sorted groups back

   Index 0->4, 3->7, 6->9
   Index 1->1, 4->5, 7->8
   Index 2->3, 5->6

4. Step 4: Final array after pass

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

5. Step 5: Check options

   [4, 8, 3, 1, 5, 6, 7, 9] is [4, 8, 3, 1, 5, 6, 7, 9], which is incorrect.
   [4, 8, 3, 7, 5, 6, 9, 1] is [4, 8, 3, 7, 5, 6, 9, 1], incorrect.
   [7, 8, 3, 1, 5, 6, 4, 9] is [7, 8, 3, 1, 5, 6, 4, 9], incorrect.
   [9, 8, 3, 7, 5, 6, 4, 1] is original array.
   None matches exactly, but the correct output after one pass is [4, 1, 3, 7, 5, 6, 9, 8]. Since not listed, the closest is none, so correct answer must be updated to reflect actual output.

6. Final Answer:

   [4, 1, 3, 7, 5, 6, 9, 8] -> No option matches exactly, so corrected answer is none of the above.

7. Quick Check:

   Shell Sort pass with gap 3 rearranges distant elements correctly [OK]

Hint: Group elements by gap and sort each group separately [OK]

Common Mistakes:

• Sorting entire array instead of gap groups
• Mixing up indices when placing sorted elements
• Ignoring elements not in full groups

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

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

medium

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

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

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

D. The variable j is used outside its scope in arr[j] = temp.

Solution

1. Step 1: Analyze loop conditions and variables

   The inner loop uses j >= gap to ensure correct comparisons and shifting.

2. Step 2: Check gap update and variable scope

   Using gap /= 2 is standard for Shell Sort; j is declared outside inner loop and accessible.

3. Final Answer:

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

4. Quick Check:

   Code correctness = No error [OK]

Hint: Check loop conditions and variable scopes carefully [OK]

Common Mistakes:

• Misreading loop boundary conditions
• Assuming variable scope errors without checking declarations
• Confusing gap update rules

5. Given an array [23, 12, 1, 8, 34, 54, 2, 3], what will be the final sorted array after applying Shell Sort with gap sequence gap = gap / 2 until gap is 0?

hard

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

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

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

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

Solution

1. Step 1: Apply Shell Sort passes with gap sequence

   Start with gap = 8/2 = 4, then 2, then 1.

2. Step 2: Sort elements at each gap

   Gap 4 pass sorts elements at indices (0,4), (1,5), (2,6), (3,7).
   After gap 4 pass, array partially sorted.
   Gap 2 pass sorts elements at indices (0,2,4,6) and (1,3,5,7).
   Gap 1 pass is normal insertion sort final pass.

3. Step 3: Final sorted array

   After all passes, array becomes [1, 2, 3, 8, 12, 23, 34, 54].

4. Final Answer:

   [1, 2, 3, 8, 12, 23, 34, 54] -> Option A

5. Quick Check:

   Shell Sort final sorted array = ascending order [OK]

Hint: Shell Sort ends with gap 1, which is insertion sort [OK]

Common Mistakes:

• Stopping before gap reaches 1
• Not sorting groups correctly at each gap
• Confusing gap sequence or final order