Shell Sort Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the gap for Shell Sort.

DSA Javascript

let n = arr.length;
let gap = [1];

Drag options to blanks, or click blank then click option'

A1

Bn

CMath.floor(n / 2)

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting gap to 0 causes no sorting steps.

Setting gap to n means no initial gap reduction.

The gap starts as half the array length, which helps compare distant elements first.

2fill in blank

medium

Complete the code to reduce the gap after each pass in Shell Sort.

DSA Javascript

while (gap > 0) {
  // sorting logic here
  gap = [1];
}

Drag options to blanks, or click blank then click option'

AMath.floor(gap / 2)

Bgap - 1

Cgap * 2

Dgap + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Increasing the gap causes infinite loops.

Subtracting 1 may not reduce gap properly for large arrays.

The gap is reduced by half each time to gradually compare closer elements.

3fill in blank

hard

Fix the error in the inner loop condition to correctly perform insertion sort with the gap.

DSA Javascript

for (let i = gap; i < n; i++) {
  let temp = arr[i];
  let j = i;
  while (j >= gap && arr[j - [1]] > temp) {
    arr[j] = arr[j - gap];
    j -= gap;
  }
  arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

Agap

B1

Ci

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 causes incorrect comparisons and sorting.

Using i or n causes index errors.

The inner loop compares elements that are 'gap' positions apart, so subtract gap.

4fill in blank

hard

Fill both blanks to complete the gap-based insertion sort step inside the while loop.

DSA Javascript

while (j >= [1] && arr[j - [2]] > temp) {
  arr[j] = arr[j - gap];
  j -= gap;
}

Drag options to blanks, or click blank then click option'

Agap

B1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of gap causes wrong element comparisons.

Using 0 causes index errors.

Both blanks use 'gap' because the sorting compares and shifts elements gap positions apart.

5fill in blank

hard

Fill all three blanks to complete the Shell Sort function.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

AMath.floor(n / 2)

Bgap

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of gap in the while loop causes incorrect sorting.

Not initializing gap properly causes no sorting.

The gap starts at half the array length, and the inner loop uses gap to compare and shift elements.

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