Shell Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array and initial gap

↓

Compare elements gap apart

↓

Swap if out of order

↓

Reduce gap

↓

Repeat until gap = 1 and array sorted

↓

Done

Shell Sort starts with a big gap between elements, compares and swaps them if needed, then reduces the gap until it becomes 1, finishing with a simple insertion sort.

Execution Sample

DSA Javascript

function shellSort(arr) {
  let n = arr.length;
  for (let gap = Math.floor(n/2); gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

This code sorts an array using Shell Sort by reducing the gap and inserting elements in the correct position.

Execution Table

Step	Operation	Gap	Index i	Index j	Array State	Action
1	Initialize gap	4	-	-	[23, 12, 1, 8, 34, 54, 2, 3, 7]	Set gap = floor(9/2) = 4
2	Compare and insert	4	4	4	[23, 12, 1, 8, 34, 54, 2, 3, 7]	temp=34, no swap needed
3	Compare and insert	4	5	5	[23, 12, 1, 8, 34, 54, 2, 3, 7]	temp=54, no swap needed
4	Compare and insert	4	6	6	[23, 12, 1, 8, 34, 54, 2, 3, 7]	temp=2, swap with arr[2]=1? No, 1<2, no swap
5	Compare and insert	4	7	7	[23, 12, 1, 8, 34, 54, 2, 3, 7]	temp=3, swap with arr[3]=8? Yes, shift 8 right
6	Shift	4	7	3	[23, 12, 1, 8, 34, 54, 2, 8, 7]	j=3, compare arr[-1] invalid, insert 3 at j=3
7	Compare and insert	4	8	8	[23, 12, 1, 3, 34, 54, 2, 8, 7]	temp=7, swap with arr[4]=34? Yes, shift 34 right
8	Shift	4	8	4	[23, 12, 1, 3, 34, 54, 2, 8, 34]	j=4, compare arr[0]=23 >7? Yes, shift 23 right
9	Shift	4	8	0	[23, 12, 1, 3, 23, 54, 2, 8, 34]	j=0, no more left, insert 7 at j=0
10	Array after gap=4 pass	4	-	-	[7, 12, 1, 3, 23, 54, 2, 8, 34]	Array partially sorted with gap 4
11	Reduce gap	2	-	-	[7, 12, 1, 3, 23, 54, 2, 8, 34]	Set gap = floor(4/2) = 2
12	Compare and insert	2	2	2	[7, 12, 1, 3, 23, 54, 2, 8, 34]	temp=1, swap with arr[0]=7? Yes, shift 7 right
13	Shift	2	2	0	[7, 12, 7, 3, 23, 54, 2, 8, 34]	j=0, insert 1 at j=0
14	Compare and insert	2	3	3	[1, 12, 7, 3, 23, 54, 2, 8, 34]	temp=3, swap with arr[1]=12? Yes, shift 12 right
15	Shift	2	3	1	[1, 12, 7, 12, 23, 54, 2, 8, 34]	j=1, compare arr[-1] invalid, insert 3 at j=1
16	Compare and insert	2	4	4	[1, 3, 7, 12, 23, 54, 2, 8, 34]	temp=23, no swap needed
17	Compare and insert	2	5	5	[1, 3, 7, 12, 23, 54, 2, 8, 34]	temp=54, no swap needed
18	Compare and insert	2	6	6	[1, 3, 7, 12, 23, 54, 2, 8, 34]	temp=2, swap with arr[4]=23? Yes, shift 23 right
19	Shift	2	6	4	[1, 3, 7, 12, 23, 54, 23, 8, 34]	j=4, swap with arr[2]=7? Yes, shift 7 right
20	Shift	2	6	2	[1, 3, 7, 12, 7, 54, 23, 8, 34]	j=2, swap with arr[0]=1? No, insert 2 at j=2
21	Compare and insert	2	7	7	[1, 3, 2, 12, 7, 54, 23, 8, 34]	temp=8, swap with arr[5]=54? Yes, shift 54 right
22	Shift	2	7	5	[1, 3, 2, 12, 7, 54, 23, 54, 34]	j=5, swap with arr[3]=12? Yes, shift 12 right
23	Shift	2	7	3	[1, 3, 2, 12, 7, 12, 23, 54, 34]	j=3, swap with arr[1]=3? No, insert 8 at j=3
24	Compare and insert	2	8	8	[1, 3, 2, 8, 7, 12, 23, 54, 34]	temp=34, swap with arr[6]=23? No, insert 34 at j=8
25	Array after gap=2 pass	2	-	-	[1, 3, 2, 8, 7, 12, 23, 54, 34]	Array more sorted with gap 2
26	Reduce gap	1	-	-	[1, 3, 2, 8, 7, 12, 23, 54, 34]	Set gap = floor(2/2) = 1
27	Compare and insert	1	1	1	[1, 3, 2, 8, 7, 12, 23, 54, 34]	temp=3, no swap needed
28	Compare and insert	1	2	2	[1, 3, 2, 8, 7, 12, 23, 54, 34]	temp=2, swap with arr[1]=3? Yes, shift 3 right
29	Shift	1	2	1	[1, 3, 3, 8, 7, 12, 23, 54, 34]	j=1, insert 2 at j=1
30	Compare and insert	1	3	3	[1, 2, 3, 8, 7, 12, 23, 54, 34]	temp=8, no swap needed
31	Compare and insert	1	4	4	[1, 2, 3, 8, 7, 12, 23, 54, 34]	temp=7, swap with arr[3]=8? Yes, shift 8 right
32	Shift	1	4	3	[1, 2, 3, 8, 8, 12, 23, 54, 34]	j=3, insert 7 at j=3
33	Compare and insert	1	5	5	[1, 2, 3, 7, 8, 12, 23, 54, 34]	temp=12, no swap needed
34	Compare and insert	1	6	6	[1, 2, 3, 7, 8, 12, 23, 54, 34]	temp=23, no swap needed
35	Compare and insert	1	7	7	[1, 2, 3, 7, 8, 12, 23, 54, 34]	temp=54, no swap needed
36	Compare and insert	1	8	8	[1, 2, 3, 7, 8, 12, 23, 54, 34]	temp=34, swap with arr[7]=54? Yes, shift 54 right
37	Shift	1	8	7	[1, 2, 3, 7, 8, 12, 23, 54, 54]	j=7, insert 34 at j=7
38	Array after gap=1 pass	1	-	-	[1, 2, 3, 7, 8, 12, 23, 34, 54]	Array fully sorted
39	End	0	-	-	[1, 2, 3, 7, 8, 12, 23, 34, 54]	gap=0, sorting complete

💡 gap reduced to 0, array is sorted

Variable Tracker

Variable	Start	After Step 10	After Step 25	After Step 38	Final
gap	4	4	2	1	0
i	-	8	8	8	-
j	-	varies	varies	varies	-
array	[23,12,1,8,34,54,2,3,7]	[7,12,1,3,23,54,2,8,34]	[1,3,2,8,7,12,23,54,34]	[1,2,3,7,8,12,23,34,54]	[1,2,3,7,8,12,23,34,54]

Key Moments - 3 Insights

Why do we start with a large gap and reduce it instead of just doing insertion sort?

Starting with a large gap moves elements far apart closer to their correct position quickly, reducing the total number of shifts needed in the final insertion sort with gap=1. See steps 1-10 where gap=4 partially sorts the array.

Why do we compare elements at index j and j-gap instead of adjacent elements?

Shell Sort compares elements gap apart to sort sublists independently. This allows elements to move faster towards their correct position. See steps 12-25 where gap=2 compares elements two apart.

How do we know when the array is fully sorted?

When the gap reduces to 1 and the insertion sort pass completes without swaps, the array is sorted. This is shown in steps 26-38 where gap=1 finishes sorting.

Visual Quiz - 3 Questions

Look at the execution table at step 10, what is the array state after the first gap=4 pass?

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

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

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

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

💡 Hint

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

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

A Step 25

B Step 38

C Step 26

D Step 39

💡 Hint

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

If the initial gap was set to 1 instead of floor(n/2), how would the execution_table change?

A It would have more passes with larger gaps.

B It would only have the gap=1 pass, similar to insertion sort.

C The array would be sorted faster.

D The gap would never reduce.

💡 Hint

Refer to the concept_flow and how gap controls passes.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = floor(n/2)
- Compare and swap elements gap apart
- Reduce gap by half each pass
- Repeat until gap = 1
- Final pass is insertion sort
- Efficient for medium-sized arrays

Full Transcript

Shell Sort works by sorting elements far apart first, then reducing the gap to sort closer elements. We start with a gap of half the array size, compare elements gap apart, and swap if needed. Then we reduce the gap and repeat. When gap is 1, it becomes a simple insertion sort. This method moves elements closer to their correct position faster than insertion sort alone. The execution table shows each step with the array state and pointer positions. Key moments include understanding why gap starts large, why we compare gap-apart elements, and how we know when sorting is done.

Practice

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

easy

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

B. It uses a divide and conquer approach like merge sort.

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

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

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 with other sorting methods

   Unlike merge sort or heap sort, Shell Sort uses gap-based comparisons, not divide and conquer or heap structure.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based comparisons [OK]

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

Common Mistakes:

• Confusing Shell Sort with merge sort or quicksort
• Thinking it only swaps adjacent elements like bubble sort
• Assuming it uses a heap structure

2. Which of the following is the correct syntax to start the gap value in a Shell Sort implementation in JavaScript?

easy

A. let gap = Math.floor(array.length / 2);

B. let gap = array.length * 2;

C. let gap = 0;

D. let gap = array.length + 1;

Solution

1. Step 1: Identify typical gap initialization

   Shell Sort usually starts with gap as half the array length, using Math.floor for integer division.

2. Step 2: Check each option

   let gap = Math.floor(array.length / 2); correctly sets gap to half length; others set invalid or zero gaps.

3. Final Answer:

   let gap = Math.floor(array.length / 2); -> Option A

4. Quick Check:

   Gap starts at half array length [OK]

Hint: Start gap as half array length using Math.floor [OK]

Common Mistakes:

• Setting gap to zero initially
• Using gap larger than array length
• Not using Math.floor for integer gap

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

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

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

Solution

1. Step 1: Identify elements compared with gap 3

   Elements compared are at indices (0,3,6) and (1,4,7) and (2,5). For example, 9 and 7 and 4; 8 and 5 and 1; 3 and 6.

2. Step 2: Perform insertion sort on these groups

   Sorting group (9,7,4) gives (4,7,9), (8,5,1) gives (1,5,8), (3,6) stays (3,6). After rearranging, array becomes [4,1,3,7,5,6,9,8].

3. Final Answer:

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

4. Quick Check:

   Gap 3 pass sorts distant elements [OK]

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

Common Mistakes:

• Not grouping elements by gap correctly
• Sorting entire array instead of gap groups
• Confusing indices during swaps

4. Identify the error in this Shell Sort snippet and choose the correct fix:

function shellSort(arr) {
  let gap = Math.floor(arr.length / 2);
  while (gap > 0) {
    for (let i = gap; i < arr.length; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = gap / 2;
  }
  return arr;
}

medium

A. Change while (gap > 0) to while (gap >= 0)

B. Change gap = gap / 2; to gap = Math.floor(gap / 2);

C. Change let j = i; to let j = gap;

D. Remove the inner while loop

Solution

1. Step 1: Analyze gap update

   The gap must be an integer; dividing by 2 without floor makes it a float, causing infinite loop.

2. Step 2: Fix gap update

   Using Math.floor ensures gap reduces properly and loop ends.

3. Final Answer:

   Change gap = gap / 2; to gap = Math.floor(gap / 2); -> Option B

4. Quick Check:

   Gap must be integer to avoid infinite loop [OK]

Hint: Always floor gap after division to keep it integer [OK]

Common Mistakes:

• Not flooring gap, causing infinite loop
• Changing loop conditions incorrectly
• Removing necessary inner loops

5. Given the array [23, 12, 1, 8, 34, 54, 2, 3], what will be the final sorted array after applying Shell Sort with gap sequence halving each time starting from Math.floor(length/2)?

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: Calculate initial gap and perform passes

   Initial gap = 4. After sorting groups with gap 4, array partially sorted. Then gap = 2, then gap = 1 (final insertion sort).

2. Step 2: Final sorted array after all passes

   After all gap passes, array becomes fully sorted ascending: [1, 2, 3, 8, 12, 23, 34, 54].

3. Final Answer:

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

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

Hint: Shell Sort ends with gap 1 insertion sort for full sorting [OK]

Common Mistakes:

• Stopping before gap reaches 1
• Misordering elements in final pass
• Confusing descending with ascending order