Shell Sort Algorithm & Example (with C++ code)

Sorting is a fundamental operation in computer science, and various sorting algorithms have been developed over the years. In this article, we will explore the Shell Sort algorithm, its implementation in C++, and its advantages over other sorting algorithms.

What is Shell Sort?

Shell Sort is an in-place comparison-based sorting algorithm, where we divide the input into smaller subarrays and perform an insertion sort on each subarray. The key idea is to allow the exchange of elements that are far apart, thus reducing the total number of swaps required.

It was invented by Donald Shell in 1959 as an improvement over Insertion Sort. Shell Sort performs better than Insertion Sort for large datasets due to its partial sorting approach. It is also memory efficient because does not require additional memory space beyond the input array.

Shell Sort Algorithm 

The Shell Sort algorithm can be summarized in the following steps:

1. Start with a gap value, typically the length of the array divided by 2.
2. Divide the array into subarrays of the gap size.
3. Perform an insertion sort on each subarray.
4. Reduce the gap value and repeat steps 2-3 until the gap becomes 1.
5. Perform a final insertion sort on the entire array with a gap of 1.

By sorting the subarrays with a larger gap first, it partially sorts the array, allowing for easier and more efficient final sorting.

Shell Sort Example

Let's consider an example to demonstrate the Shell Sort algorithm step-by-step:

Array: [8, 3, 9, 2, 4, 7, 5, 1, 6]

1. Initial gap = 9/2 = 4

2. Divide the array into subarrays with a gap of 4: [8, 4], [3, 7], [9, 5], [2, 1], [6] Perform an insertion sort on each subarray. Array after sorting: [4, 3, 5, 1, 6, 8, 9, 2, 7]

3. Reduce the gap to 4/2 = 2

4. Divide the array into subarrays with a gap of 2: [4, 5, 6, 9, 7], [3, 1, 8, 2] Perform an insertion sort on each subarray. Array after sorting: [4, 1, 6, 2, 7, 3, 8, 5, 9]

5. Reduce the gap to 2/2 = 1

6. Perform a final insertion sort on the entire array with a gap of 1: Array after sorting: [1, 2, 3, 4, 5, 6, 7, 8, 9]

C++ Implementation

Here's an implementation of the Shell Sort algorithm in C++:

#include<iostream>
#include<vector> 

void shellSort(std::vector<int>& arr) {
    int n = arr.size();

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

int main() {
    std::vector<int> arr = {8, 3, 9, 2, 4, 7, 5, 1, 6};

    shellSort(arr);

    std::cout << "Sorted Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
} 

Output:

Sorted Array: 1 2 3 4 5 6 7 8 9 

Time & Space Complexity

The time complexity of the Shell Sort algorithm depends on the gap sequence used. The worst-case time complexity is O(n^2), but it can be reduced to O(n log n) by using an optimized gap sequence like the Knuth sequence or Sedgewick sequence. The average and best-case time complexity it is still an open problem.

The space complexity of the Shell Sort algorithm is O(1), which means that it requires a constant amount of additional space regardless of the input size.

Is Shell Sort better than Insertion Sort?

Shell Sort is considered an improvement over Insertion Sort by many programmers, as this is why it was designed in the first place. While Insertion Sort compares adjacent elements, Shell Sort allows for comparisons of elements far apart by using the concept of gaps. This makes Shell Sort much faster than Insertion Sort for larger datasets.

However, new techniques like Quicksort and Merge Sort often outperform it in terms of both time complexity and practical efficiency. 

Is Merge Sort and Shell Sort the same?

Both are different algorithms. Merge Sort is a divide-and-conquer algorithm that divides the input into smaller subproblems, whereas Shell Sort is an incremental sorting algorithm that divides the input into subarrays. 

Merge Sort requires additional memory space and it is a stable sorting algorithm. On the other hand, Shell Sort does not require additional memory space for merging or recursion and it is not a stable sorting algorithm.

Conclusion

Shell Sort is one of the most-asked sorting algorithms in technical interviews that you must learn about. Note that its performance can be improved by using different gap sequences based on the input size.