Shell Sort Algorithm in DSA C

Mental Model

Shell sort improves simple sorting by comparing elements far apart first, then reducing the gap to sort closer elements.

Analogy: Imagine organizing books on a shelf by first sorting every 5th book, then every 3rd, and finally every book next to each other to get a fully sorted shelf.

Array: [8, 5, 3, 7, 6, 2, 4, 1]
Gap: 4
Indexes compared: 0 -> 4, 1 -> 5, 2 -> 6, 3 -> 7

Dry Run Walkthrough

Input: array: [8, 5, 3, 7, 6, 2, 4, 1]

Goal: Sort the array in ascending order using Shell sort

Step 1: Start with gap = 4, compare and sort elements 4 apart

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

Why: Sorting elements far apart moves bigger elements towards the end faster

Step 2: Reduce gap to 2, perform insertion sort on subarrays with gap 2

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

Why: Sorting closer elements refines order after big jumps

Step 3: Reduce gap to 1, perform final insertion sort on entire array

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

Why: Final pass ensures full sorted order by comparing adjacent elements

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform gapped insertion sort for this gap size
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            // Shift earlier gap-sorted elements up until correct location found
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(", ");
    }
    printf("\n");
}

int main() {
    int arr[] = {8, 5, 3, 7, 6, 2, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    printArray(arr, n);
    return 0;
}

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

start with large gap and reduce it each iteration

for (int i = gap; i < n; i++) {

iterate over elements starting from gap index

while (j >= gap && arr[j - gap] > temp) {

shift elements greater than temp up by gap distance

arr[j] = temp;

insert temp at correct position in gap-sorted subarray

Output

1, 2, 3, 4, 5, 6, 7, 8

Complexity Analysis

Time: O(n^(3/2)) average and worst case because gap sequence reduces comparisons gradually

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Faster than simple insertion sort O(n^2) on large arrays by reducing total shifts with gap sorting

Edge Cases

empty array

function completes immediately without changes

DSA C

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

array with one element

array remains unchanged as it is already sorted

DSA C

for (int i = gap; i < n; i++) {

array with all elements equal

no swaps occur, array remains the same

DSA C

while (j >= gap && arr[j - gap] > temp) {

When to Use This Pattern

When you need to improve insertion sort by comparing elements far apart first, use Shell sort to reduce total shifts and speed up sorting.

Common Mistakes

Mistake: Not reducing the gap properly (e.g., not dividing by 2 each time)
Fix: Ensure gap is updated by dividing by 2 each iteration to eventually reach 1

Mistake: Incorrectly shifting elements in the inner while loop causing wrong order
Fix: Shift elements only while they are greater than temp and within array bounds

Summary

Shell sort sorts by comparing elements far apart and gradually reducing the gap to fully sort the array.

Use Shell sort when you want a faster in-place sort than insertion sort for medium-sized arrays.

The key insight is that sorting distant elements first reduces the total work needed in the final passes.

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