Shell Sort Algorithm in DSA C++ - Build from Scratch

Shell Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Shell Sort is a sorting technique that improves on simple sorting methods by comparing elements far apart and gradually reducing the gap between elements to be compared.Imagine you have a messy stack of numbered cards, and you want to arrange them in order. Instead of sorting one card at a time, you first compare cards far apart, then closer, until everything is sorted.

🎯 Goal: Build a C++ program that sorts an array of integers using the Shell Sort algorithm. You will create the array, set the initial gap, implement the sorting logic, and finally print the sorted array.

📋 What You'll Learn

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

Create an integer variable n to store the size of the array

Create an integer variable gap initialized to half of n

Implement the Shell Sort algorithm using a while loop that reduces gap until it becomes 0

Use nested for and while loops to perform insertion sort on elements separated by gap

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Shell Sort is useful in systems where simple sorting algorithms are too slow but full quicksort is too complex. It is often used in embedded systems or small datasets.

💼 Career

Understanding Shell Sort helps in grasping how sorting algorithms optimize comparisons and swaps, a key skill in software development and technical interviews.

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++

int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
// Your code here

Hint

Use sizeof(arr) / sizeof(arr[0]) to find the number of elements in the array.

2

Set the initial gap for Shell Sort

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

DSA C++

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

Hint

The gap starts as half the size of the array.

3

Implement the Shell Sort algorithm

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. Then use a while loop with variable j to perform insertion sort on elements separated by gap. Decrease gap by half at the end of each while loop iteration.

DSA C++

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

Hint

Shell Sort uses a gap to compare and sort elements far apart, then reduces the gap gradually.

4

Print the sorted array

Use a for loop with variable i from 0 to n to print each element of arr separated by spaces.

DSA C++

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

while (gap > 0) {
    for (int i = gap; i = gap && arr[j - gap] > temp) {
            arr[j] = arr[j - gap];
            j -= gap;
        }
        arr[j] = temp;
    }
    gap /= 2;
}
// Your code here

Hint

Print each element followed by a space. Use std::cout and end with std::endl.

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