Shell Sort Algorithm in DSA C - Build from Scratch

Shell Sort Algorithm

📖 Scenario: You have a list of numbers that you want to sort to organize your data better. Sorting helps you find things faster, like arranging books by their size on a shelf.

🎯 Goal: You will build a program that sorts an array of numbers using the Shell Sort algorithm, which is a faster way to sort than simple methods.

📋 What You'll Learn

Create an array called arr with the exact values: 23, 12, 1, 8, 34, 54, 2, 3

Create an integer variable called n that stores the size of the array

Create an integer variable called gap to control the distance between compared elements

Use a while loop to reduce the gap until it becomes zero

Use nested for loops to compare and swap elements separated by gap

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing files, searching data quickly, or arranging items in a store.

💼 Career

Understanding sorting algorithms like Shell Sort helps in software development, data analysis, and optimizing performance.

1

Create the array and its size

Create an integer array called arr with these exact values: 23, 12, 1, 8, 34, 54, 2, 3. Then create an integer variable called n and set it to the size of arr.

DSA C

#include 

int main() {
    // Create the array arr with values 23, 12, 1, 8, 34, 54, 2, 3
    // Create the integer n as the size of arr
    // Your code here

    return 0;
}

Hint

Use int arr[] = {23, 12, 1, 8, 34, 54, 2, 3}; to create the array. Use sizeof(arr) / sizeof(arr[0]) to find the size.

2

Initialize the gap variable

Create an integer variable called gap and set it to half of n using integer division.

DSA C

#include 

int main() {
    int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // Create the gap variable and set it to n divided by 2
    // Your code here

    return 0;
}

Hint

Use int gap = n / 2; to set the initial gap.

3

Implement the Shell Sort logic

Use a while loop that runs while gap is greater than 0. Inside it, use a for loop with variable i from gap to n - 1. Then create an integer temp to store arr[i]. Use another for loop with variable j starting from i and decreasing by gap while j >= gap and arr[j - gap] > temp. Inside this inner loop, assign arr[j] = arr[j - gap]. After the inner loop, assign arr[j] = temp. Finally, reduce gap by dividing it by 2.

DSA C

#include 

int main() {
    int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int gap = n / 2;

    // Implement the Shell Sort algorithm using while and for loops
    // Your code here

    return 0;
}

Hint

Use nested loops: a while for gap, a for for i, and a for for j to shift elements. Remember to update gap by dividing by 2.

4

Print the sorted array

Use a for loop with variable i from 0 to n - 1 to print each element of arr followed by a space. Then print a newline character.

DSA C

Hint

Use a for loop to print each element with printf("%d ", arr[i]); and then print a newline with printf("\n");.

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