Shell Sort Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the gap for Shell Sort.

DSA C

int n = sizeof(arr)/sizeof(arr[0]);
int gap = [1];

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

An - 1

Bn * 2

Cn / 2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting gap to the full array length causes no initial sorting.

Setting gap to 1 from the start makes it a simple insertion sort.

The initial gap in Shell Sort is usually set to half the array size.

2fill in blank

medium

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

DSA C

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

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

Agap / 2

Bgap / 3

Cgap - 1

Dgap * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying gap increases it, causing infinite loop.

Subtracting 1 may not reduce gap efficiently.

Gap is reduced by half each iteration until it reaches zero.

3fill in blank

hard

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

DSA C

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

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

A<=

B>

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes incorrect sorting order.

Using '>=' may cause unnecessary shifts.

The condition arr[j - gap] > temp ensures elements are shifted if they are greater than temp.

4fill in blank

hard

Fill both blanks to complete the Shell Sort gap reduction and loop condition.

DSA C

int gap = n / 2;
while ([1] > 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];
}

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

Agap

Bn

Cgap / 2

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'n' in the while condition causes infinite loop.

Using 'i' for gap update is incorrect.

The outer loop continues while gap > 0, and gap is halved each iteration.

5fill in blank

hard

Fill all three blanks to complete the Shell Sort implementation and print the sorted array.

DSA C

int n = sizeof(arr)/sizeof(arr[0]);
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] [1] temp) {
            arr[j] = arr[j - gap];
            j -= gap;
        }
        arr[j] = temp;
    }
    gap = [2];
}

// Print sorted array
for (int k = 0; k < n; k++) {
    printf("%d ", arr[[3]]);
}

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

A>

Bgap / 2

Ck

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' in comparison causes wrong sorting.

Using wrong variable for printing index causes errors.

The comparison uses '>', gap is halved each iteration, and printing uses index k.

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 uses a divide and conquer approach like merge sort.

C. It builds a heap and extracts the maximum element repeatedly.

D. It repeatedly swaps adjacent elements if they are in wrong order.

Solution

1. Step 1: Understand Shell Sort concept

   Shell Sort improves insertion sort by comparing elements far apart, not just adjacent ones.

2. Step 2: Identify the gap reduction

   The algorithm starts with a large gap and reduces it until it becomes 1, sorting elements at each gap.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap comparison and reduction [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax to start the gap value in Shell Sort for an array of size n in C?

easy

A. int gap = n * 2;

B. int gap = n - 1;

C. int gap = n / 2;

D. int gap = 1;

Solution

1. Step 1: Identify typical initial gap

   Shell Sort usually starts with gap as half the array size, so gap = n / 2.

2. Step 2: Check other options

   Multiplying by 2 or using n-1 is not standard; starting at 1 is too small for initial gap.

3. Final Answer:

   int gap = n / 2; -> Option C

4. Quick Check:

   Initial gap = n/2 [OK]

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

Common Mistakes:

• Starting gap at 1 instead of n/2
• Using n*2 which is too large
• Using n-1 which is not standard

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

C. [4, 8, 3, 7, 5, 6, 9, 1]

D. [4, 8, 3, 1, 5, 6, 7, 9]

Solution

1. Step 1: Identify elements compared with gap 3

   Elements compared are at indices (0,3,6), (1,4,7), and (2,5).

2. Step 2: Sort elements in these groups

   Group 1: [9,7,4] sorted -> [4, 8, 3, 1, 5, 6, 7, 9]

3. Step 3: Place sorted groups back

   Index 0->4, 3->7, 6->9
   Index 1->1, 4->5, 7->8
   Index 2->3, 5->6

4. Step 4: Final array after pass

   [4, 1, 3, 7, 5, 6, 9, 8]

5. Step 5: Check options

   [4, 8, 3, 1, 5, 6, 7, 9] is [4, 8, 3, 1, 5, 6, 7, 9], which is incorrect.
   [4, 8, 3, 7, 5, 6, 9, 1] is [4, 8, 3, 7, 5, 6, 9, 1], incorrect.
   [7, 8, 3, 1, 5, 6, 4, 9] is [7, 8, 3, 1, 5, 6, 4, 9], incorrect.
   [9, 8, 3, 7, 5, 6, 4, 1] is original array.
   None matches exactly, but the correct output after one pass is [4, 1, 3, 7, 5, 6, 9, 8]. Since not listed, the closest is none, so correct answer must be updated to reflect actual output.

6. Final Answer:

   [4, 1, 3, 7, 5, 6, 9, 8] -> No option matches exactly, so corrected answer is none of the above.

7. Quick Check:

   Shell Sort pass with gap 3 rearranges distant elements correctly [OK]

Hint: Group elements by gap and sort each group separately [OK]

Common Mistakes:

• Sorting entire array instead of gap groups
• Mixing up indices when placing sorted elements
• Ignoring elements not in full groups

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

void shellSort(int arr[], int n) {
  int gap, i, j, temp;
  for (gap = n/2; gap > 0; gap /= 2) {
    for (i = gap; i < n; i++) {
      temp = arr[i];
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

medium

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

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

C. The gap update should be gap = gap / 3, not gap /= 2.

D. The variable j is used outside its scope in arr[j] = temp.

Solution

1. Step 1: Analyze loop conditions and variables

   The inner loop uses j >= gap to ensure correct comparisons and shifting.

2. Step 2: Check gap update and variable scope

   Using gap /= 2 is standard for Shell Sort; j is declared outside inner loop and accessible.

3. Final Answer:

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

4. Quick Check:

   Code correctness = No error [OK]

Hint: Check loop conditions and variable scopes carefully [OK]

Common Mistakes:

• Misreading loop boundary conditions
• Assuming variable scope errors without checking declarations
• Confusing gap update rules

5. Given an array [23, 12, 1, 8, 34, 54, 2, 3], what will be the final sorted array after applying Shell Sort with gap sequence gap = gap / 2 until gap is 0?

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: Apply Shell Sort passes with gap sequence

   Start with gap = 8/2 = 4, then 2, then 1.

2. Step 2: Sort elements at each gap

   Gap 4 pass sorts elements at indices (0,4), (1,5), (2,6), (3,7).
   After gap 4 pass, array partially sorted.
   Gap 2 pass sorts elements at indices (0,2,4,6) and (1,3,5,7).
   Gap 1 pass is normal insertion sort final pass.

3. Step 3: Final sorted array

   After all passes, array becomes [1, 2, 3, 8, 12, 23, 34, 54].

4. Final Answer:

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

5. Quick Check:

   Shell Sort final sorted array = ascending order [OK]

Hint: Shell Sort ends with gap 1, which is insertion sort [OK]

Common Mistakes:

• Stopping before gap reaches 1
• Not sorting groups correctly at each gap
• Confusing gap sequence or final order