Shell Sort Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Shell Sort with gap sequence

What is the output of the following Java code after performing Shell Sort on the array?

DSA Java

public class ShellSortTest {
    public static void main(String[] args) {
        int[] arr = {23, 12, 1, 8, 34, 54, 2, 3};
        shellSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void shellSort(int[] arr) {
        int n = arr.length;
        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;
            }
        }
    }
}

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

💡 Hint

Shell Sort sorts the array 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 results in a sorted array in ascending order.

🧠 Conceptual

intermediate

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 quickly, improving performance over simple insertion sort.

B Using a gap of 1 from the start is the most efficient way to sort with Shell Sort.

C The gap sequence does not affect the performance; only the array size matters.

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

💡 Hint

Think about how elements move across the array during sorting.

Starting with a larger gap allows elements to move farther in fewer steps, reducing the total number of comparisons and swaps compared to simple insertion sort.

🔧 Debug

advanced

Identify the error in Shell Sort implementation

What error will occur when running this Shell Sort code snippet?

DSA Java

public static void shellSort(int[] arr) {
    int n = arr.length;
    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;
        }
    }
}

A No error; code runs correctly and sorts the array

B ArrayIndexOutOfBoundsException due to incorrect index in while condition

C NullPointerException because array is not initialized

D Infinite loop because gap never decreases

💡 Hint

Check the index used inside the while loop condition carefully.

The condition uses arr[j + gap] which can go beyond array bounds. It should be arr[j - gap] to compare with the element gap positions before.

📝 Syntax

advanced

Syntax error in Shell Sort code

Which option contains the correct syntax to declare and initialize the gap variable in Shell Sort?

A for (int gap = n / 2; gap > 0; gap = / 2) {

B for (int gap = n / 2; gap > 0; gap = gap / 2) {

C for (int gap = n / 2; gap > 0; gap /= 2) {

D for (int gap = n / 2; gap > 0; gap = gap // 2) {

💡 Hint

Look for the correct shorthand operator for division assignment.

The operator '/=' divides the variable by the right-hand value and assigns the result back to the variable. Other options use longer syntax or have syntax errors or invalid operators.

🚀 Application

expert

Shell Sort on a large nearly sorted array

You have a large array that is almost sorted except for a few elements far from their correct position. Which property of Shell Sort makes it suitable for this scenario?

A Shell Sort uses extra memory to handle large arrays efficiently.

B Shell Sort always performs worse than insertion sort on nearly sorted arrays.

C Shell Sort sorts only the first half of the array, leaving the rest untouched.

D Shell Sort efficiently moves elements far apart early, reducing total shifts needed.

💡 Hint

Consider how Shell Sort handles elements that are far from their final position.

Shell Sort's gap-based comparisons allow it to move elements that are far apart closer to their correct position quickly, making it efficient for nearly sorted arrays with some misplaced elements.

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