Shell Sort Algorithm in DSA C++ - 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 input array [23, 12, 1, 8, 34, 54, 2, 3] using the gap sequence [4, 2, 1]?

DSA C++

void shellSort(int arr[], int n) {
    int gaps[] = {4, 2, 1};
    for (int gap : gaps) {
        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;
        }
    }
}

int main() {
    int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    shellSort(arr, n);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

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

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

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

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

💡 Hint

Shell Sort sorts the array by comparing elements at a certain gap and reducing the gap gradually until it becomes 1.

Shell Sort starts with a large gap and sorts elements far apart from each other. Then it reduces the gap and sorts again. Finally, it does a normal insertion sort with gap 1. This results in a sorted array.

🧠 Conceptual

intermediate

Understanding the role of gap sequence in Shell Sort

Why does Shell Sort use a gap sequence instead of just sorting adjacent elements like Insertion Sort?

A Because it avoids sorting the array completely.

B Because sorting elements far apart first reduces the total number of swaps needed later.

C Because it only works on arrays with even length.

D Because it makes the algorithm run slower and more complex.

💡 Hint

Think about how sorting far apart elements can help bring the array closer to sorted faster.

Sorting elements far apart helps move elements closer to their final position quickly. This reduces the total work needed when the gap becomes 1, making the algorithm faster than simple insertion sort.

🔧 Debug

advanced

Identify the error in this Shell Sort implementation

What error will this Shell Sort code produce when run?

DSA C++

void shellSort(int arr[], int n) {
    int gap = n / 2;
    while (gap > 0) {
        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;
        }
        gap /= 2;
    }
}

A The code will not compile due to syntax errors.

B The code will cause a runtime error due to invalid array access.

C The array will be sorted in descending order, not ascending.

D The array will remain unsorted.

💡 Hint

Check the comparison operator inside the inner while loop.

The comparison uses '<' instead of '>'. This causes the algorithm to sort the array in descending order instead of ascending order.

📝 Syntax

advanced

Find the syntax error in this Shell Sort code snippet

Which option correctly fixes the syntax error in the following code? for (int gap : gaps) { 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; } }

DSA C++

int gaps[] = {5, 3, 1};
int n = 10;
int arr[10];

A Remove the semicolon after 'arr[j] = temp;'

B Change 'for (int gap : gaps)' to 'for int gap in gaps'

C Replace 'while' with 'if' in the inner loop

D Add a semicolon after 'int temp = arr[i]'

💡 Hint

Check for missing punctuation after variable declarations.

The line 'int temp = arr[i]' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Choosing the best gap sequence for Shell Sort

Which gap sequence is known to provide better average performance for Shell Sort compared to simple halving (n/2, n/4, ...)?

A Using the sequence of gaps as the Ciura sequence (e.g., 701, 301, 132, 57, 23, 10, 4, 1)

B Using the sequence of gaps as powers of two (e.g., 8, 4, 2, 1)

C Using the sequence of gaps as Fibonacci numbers (e.g., 13, 8, 5, 3, 2, 1)

D Using the sequence of gaps as prime numbers only (e.g., 17, 13, 7, 3, 1)

💡 Hint

Some gap sequences are experimentally proven to reduce the number of comparisons and swaps.

The Ciura sequence is a well-known gap sequence that improves Shell Sort's efficiency by reducing the number of comparisons and swaps compared to simple halving.

Practice

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

easy

A. It sorts elements by building a binary heap.

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

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

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

Solution

1. Step 1: Understand Shell Sort's approach

   Shell Sort starts by comparing elements far apart using a gap, not just neighbors.

2. Step 2: Gap reduction and sorting

   The gap reduces gradually until it becomes 1, performing insertion sort at each stage.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based sorting [OK]

Hint: Remember: Shell Sort uses gaps that shrink over time [OK]

Common Mistakes:

• Thinking Shell Sort only swaps adjacent elements
• Confusing Shell Sort with merge or heap sort
• Ignoring the gap reduction step

2. Which of the following is the correct way to initialize the gap in Shell Sort for an array of size n in C++?

easy

A. int gap = n / 2;

B. int gap = n * 2;

C. int gap = n + 1;

D. int gap = 1;

Solution

1. Step 1: Identify the common gap initialization

   Shell Sort commonly starts with gap as half the array size, i.e., n/2.

2. Step 2: Check other options

   Multiplying or adding to n is incorrect; starting at 1 skips the gap sorting steps.

3. Final Answer:

   int gap = n / 2; -> Option A

4. Quick Check:

   Gap starts at half array size [OK]

Hint: Gap usually starts at half the array length [OK]

Common Mistakes:

• Starting gap at 1 instead of n/2
• Using gap larger than array size
• Confusing gap initialization with loop counters

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

medium

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

Solution

1. Step 1: Apply Shell Sort steps on the array

   Start with gap = 4 (8/2), sort elements 4 apart, then gap = 2, then gap = 1.

2. Step 2: Final sorted array

   After all gap reductions and sorting, 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 A

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

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

Common Mistakes:

• Confusing partial sorted arrays as final output
• Reversing the array order
• Ignoring gap-based sorting steps

4. Identify the error in the following Shell Sort code snippet:

void shellSort(int arr[], int n) {
  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;
    }
  }
}

medium

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

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

C. The gap should start from n, not n/2.

D. The gap update should be gap = gap - 1 instead of gap /= 2.

Solution

1. Step 1: Review gap initialization and update

   Gap starts at n/2 and halves each iteration, which is correct for Shell Sort.

2. Step 2: Check inner loop and conditions

   The while loop uses j >= gap to avoid out-of-bound and correctly shifts elements.

3. Final Answer:

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

4. Quick Check:

   Code matches Shell Sort logic [OK]

Hint: Check gap halving and while loop conditions carefully [OK]

Common Mistakes:

• Changing gap update to subtract 1 breaks algorithm
• Using incorrect while loop boundary causes errors
• Starting gap at n causes out-of-bound issues

5. Given an array arr = {23, 12, 1, 8, 34, 54, 2, 3}, how many times will the inner while loop execute during the first gap iteration (gap = 4) in Shell Sort?

hard

A. 5 times

B. 4 times

C. 3 times

D. 6 times

Solution

1. Step 1: Identify elements compared with gap = 4

   Pairs compared: (23, 34), (12, 54), (1, 2), (8, 3).

2. Step 2: Count while loop executions

   Only pairs where left element > right element cause shifts. Here, (23 > 34) no, (12 > 54) no, (1 > 2) no, (8 > 3) yes. For (8,3), shifting occurs once. Also, elements at indices 4 to 7 are checked, total 4 iterations of the outer loop, but only 1 inner while loop execution occurs.

3. Final Answer:

   3 times -> Option C

4. Quick Check:

   Count actual inner while loop executions, not just comparisons [OK]

Hint: Count pairs separated by gap and check conditions [OK]

Common Mistakes:

• Counting only swaps, not all while loop checks
• Ignoring elements beyond first gap iteration
• Misunderstanding gap-based comparisons