Shell Sort Algorithm in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the gap for Shell Sort.

DSA Java

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

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

An / 2

Bn + 1

Cn * 2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using gap as the full length of the array.

Starting gap at 1 instead of half the array length.

The Shell Sort starts with a gap of half the array length to compare elements far apart.

2fill in blank

medium

Complete the code to reduce the gap in each iteration of Shell Sort.

DSA Java

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

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

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying the gap instead of dividing.

Subtracting 2 from the gap which may cause negative values.

The gap is reduced by dividing it by 2 in each iteration to gradually sort the array.

3fill in blank

hard

Fix the error in the inner loop condition to correctly compare elements in Shell Sort.

DSA Java

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

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

Agap

Bi

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using gap as the boundary which may cause skipping elements.

Using i or n which are incorrect for index boundary.

The inner loop must continue while j is greater than or equal to 0 to avoid index errors.

4fill in blank

hard

Fill both blanks to complete the insertion step inside the Shell Sort inner loop.

DSA Java

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

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

A0

Bj - gap

Cj + gap

Dgap

Attempts:

3 left

💡 Hint

Common Mistakes

Using gap instead of 0 for boundary check.

Using j+gap which causes index out of bounds.

The loop continues while j is at least 0, and elements are shifted from index j-gap to j.

5fill in blank

hard

Fill all three blanks to complete the Shell Sort method.

DSA Java

public void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = [1]; gap > 0; gap = gap [2] 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= [3] && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

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

An / 2

B/

C0

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division to reduce gap.

Incorrect boundary check causing index errors.

The Shell Sort starts with gap = n/2, reduces gap by dividing by 2, and the inner loop boundary is zero.

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 sorts elements by repeatedly swapping adjacent elements only.

C. It uses a divide and conquer approach to sort subarrays independently.

D. It builds a sorted list by inserting elements one by one in order.

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 options with concept

   It sorts elements by comparing distant elements and gradually reducing the gap. correctly describes this gap reduction and distant element comparison. Others describe different sorting methods.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap reduction and distant comparisons [OK]

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

Common Mistakes:

• Confusing Shell Sort with Bubble Sort
• Thinking it only swaps adjacent elements
• Mixing it up with Merge Sort or Insertion Sort

2. Which of the following is the correct way to initialize the gap variable in Shell Sort in Java?

easy

A. int gap = arr.length / 2;

B. int gap = arr.length * 2;

C. int gap = arr.length + 1;

D. int gap = 0;

Solution

1. Step 1: Understand gap initialization

   Shell Sort starts with a gap usually half the array length to compare distant elements.

2. Step 2: Check options for correct initialization

   int gap = arr.length / 2; correctly sets gap to half the array length. Others are incorrect or ineffective.

3. Final Answer:

   int gap = arr.length / 2; -> Option A

4. Quick Check:

   Gap starts at half array length [OK]

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

Common Mistakes:

• Setting gap larger than array length
• Starting gap at zero causing no sorting
• Using gap as array length plus one

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

medium

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

Solution

1. Step 1: Apply Shell Sort on given array

   Start with gap = 4 (8/2), compare and swap distant elements, then reduce gap to 2, then 1, sorting progressively.

2. Step 2: Final sorted array

   After all gap reductions and swaps, 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 D

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

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

Common Mistakes:

• Confusing partial sorted states as final output
• Ignoring gap reductions
• Assuming reverse order output

4. Identify the error in this Shell Sort snippet:

for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  for (int i = gap; i < arr.length; 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 gap update should be gap = gap / 3, not gap /= 2.

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

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

D. The variable temp should be declared outside the loops.

Solution

1. Step 1: Analyze the loop and conditions

   The gap starts at half array length and halves each iteration, which is a common Shell Sort approach.

2. Step 2: Check inner loop and assignments

   The inner while loop correctly shifts elements greater than temp, and temp is assigned properly after shifting.

3. Final Answer:

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

4. Quick Check:

   Code matches standard Shell Sort logic [OK]

Hint: Check loop conditions and assignments carefully [OK]

Common Mistakes:

• Changing gap update incorrectly
• Misusing loop conditions causing index errors
• Declaring variables in wrong scope

5. Given an array int[] arr = {20, 35, -15, 7, 55, 1, -22};, how many times will the inner while loop execute during the first gap iteration in Shell Sort?

hard

A. 5 times

B. 3 times

C. 7 times

D. 9 times

Solution

1. Step 1: Determine initial gap

   Array length 7, gap = 3. Process i from 3 to 6.

2. Step 2: Count inner while loop executions (shifts)

   Initial: [20,35,-15,7,55,1,-22]
   - i=3, temp=7 vs arr[0]=20: 1 shift -> [7,35,-15,20,55,1,-22]
   - i=4, temp=55 vs arr[1]=35: 0 shifts (35 < 55)
   - i=5, temp=1 vs arr[2]=-15: 0 shifts (-15 < 1)
   - i=6, temp=-22 vs arr[3]=20 then arr[0]=7: 2 shifts
   Total: 1+0+0+2 = 3.

3. Final Answer:

   3 times -> Option B

4. Quick Check:

   Shifts first gap = 3 [OK]

Hint: Count shifts for each gap iteration carefully [OK]

Common Mistakes:

• Counting only comparisons, not shifts
• Ignoring multiple shifts per element
• Miscalculating gap or indices