Shell Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Shell Sort with a specific gap sequence

What is the output array after running the Shell Sort algorithm on the array [23, 12, 1, 8, 34, 54, 2, 3] using the gap sequence [4, 2, 1]?

DSA Javascript

function shellSort(arr) {
  let gaps = [4, 2, 1];
  for (let gap of gaps) {
    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;
    }
  }
  return arr;
}

console.log(shellSort([23, 12, 1, 8, 34, 54, 2, 3]));

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

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

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

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

💡 Hint

Shell Sort sorts elements by comparing elements at a certain gap and reducing the gap gradually.

Shell Sort starts with a large gap and sorts elements that are far apart. Then it reduces the gap and sorts again until the gap is 1, which is a normal insertion sort. This process results in a sorted array.

🧠 Conceptual

intermediate

Understanding the gap sequence effect in Shell Sort

Which statement best describes the effect of the gap sequence on the Shell Sort algorithm's performance?

A A larger initial gap helps move elements farther apart closer to their final position early, improving efficiency.

B The gap sequence does not affect the sorting performance; it only changes the order of comparisons.

C A smaller initial gap leads to faster sorting because fewer elements are compared.

D Using a gap sequence of only 1 is the most efficient way to perform Shell Sort.

💡 Hint

Think about how moving elements far apart early can reduce the total number of moves later.

Starting with a larger gap allows the algorithm to move elements that are far apart closer to their correct positions early, which reduces the total number of comparisons and shifts needed in later passes.

🔧 Debug

advanced

Identify the error in this Shell Sort implementation

What error does the following Shell Sort code produce when run?

DSA Javascript

function shellSort(arr) {
  let n = arr.length;
  let gap = Math.floor(n / 2);
  while (gap > 0) {
    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;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

console.log(shellSort([5, 3, 8, 4, 2]));

A The code runs but outputs an incorrectly sorted array [8, 5, 4, 3, 2]

B The code runs and outputs [5, 3, 8, 4, 2]

C The code runs and outputs [2, 3, 4, 5, 8]

D The code runs and outputs [8, 5, 4, 3, 2]

💡 Hint

Check the comparison operator in the inner while loop.

The comparison operator in the inner while loop is '<' which causes the array to be sorted in descending order incorrectly. Shell Sort should use '>' to sort in ascending order.

📝 Syntax

advanced

Identify the syntax error in this Shell Sort snippet

Which option correctly fixes the syntax error in the following code snippet?

DSA Javascript

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

A Replace 'let' with 'var' for all variable declarations.

B Remove the Math.floor calls from the gap calculation.

C Change 'while' to 'if' in the inner loop condition.

D Add semicolons at the end of lines missing them inside the loops.

💡 Hint

JavaScript requires semicolons to separate statements, especially inside loops.

The code is missing semicolons at the end of some statements, which can cause syntax errors or unexpected behavior. Adding semicolons fixes the syntax.

🚀 Application

expert

Shell Sort on a large nearly sorted array

Given a nearly sorted array of 1000 elements where only 10 elements are out of place, which gap sequence would likely give the best performance for Shell Sort?

A A gap sequence with random gaps unrelated to array size

B A gap sequence of only 1 (normal insertion sort)

C A gap sequence with small gaps only (e.g., 5, 3, 1)

D A gap sequence that starts large and reduces by half each time (e.g., 500, 250, 125, ... 1)

💡 Hint

Nearly sorted arrays benefit from small gaps to quickly fix minor disorder.

For nearly sorted arrays, small gap sequences like (5, 3, 1) help quickly fix the few misplaced elements with minimal overhead, making the sort efficient.

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