Shell Sort Algorithm in DSA C - Time & Space Complexity

Time Complexity: Shell Sort Algorithm

O(n^(3/2))

Understanding Time Complexity

We want to understand how the time taken by Shell Sort changes as the list size grows.

How does the number of steps grow when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following 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;
        }
    }
}

This code sorts an array by comparing elements far apart and gradually reducing the gap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner while loop that shifts elements to insert the current element in the right place.
• How many times: The outer for loop reduces the gap roughly by half each time, and the inner loops run depending on the gap and array size.

How Execution Grows With Input

As the list size grows, the number of comparisons and shifts grows faster than the list size but slower than simple quadratic growth.

Input Size (n)	Approx. Operations
10	About 20-30 operations
100	About 700-1000 operations
1000	About 20,000-30,000 operations

Pattern observation: The operations grow faster than linear but slower than quadratic, roughly between n log n and n squared.

Final Time Complexity

Time Complexity: O(n^{3/2})

This means the time grows faster than n log n but slower than n squared, so it is more efficient than simple bubble or insertion sort on large lists.

Common Mistake

[X] Wrong: "Shell Sort always runs in O(n log n) time like Merge Sort."

[OK] Correct: Shell Sort's time depends on the gap sequence and can be worse than O(n log n), often around O(n^{3/2}) or more, so it is not as fast as Merge Sort in the worst case.

Interview Connect

Understanding Shell Sort's time complexity helps you compare sorting methods and shows you can analyze algorithms beyond simple cases.

Self-Check

"What if we changed the gap sequence to use a different pattern, like the Knuth sequence? How would the time complexity change?"

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