Shell Sort In C++

In the field of computer science, sorting algorithms play a crucial role in organizing data systematically. Various types of sorting algorithms exist, each with its unique set of pros and cons. Among these is the Shell sort, also known as the diminishing increment sort, which stands out as a popular choice. This article will delve into the intricacies of the Shell sort algorithm and demonstrate how to implement it using C++.

An array gets organized through the shell sort technique, which involves comparing entries that are not adjacent but far apart. The process kicks off by utilizing a gap sequence to divide the array into smaller subarrays, known as h-sorted arrays. The distances between the elements to be compared are indicated by the gap sequence, which comprises a series of numbers. The gap sequence calculation often relies on the Knuth sequence, obtained through the formula 3k - 1, where k represents an integer.

Afterwards, the algorithm performs an insertion sort on each subarray once the subarrays have been created. Each insertion sort is a simple sorting technique that examines the position of each element relative to its adjacent elements and swaps them when needed. The insertion sort is executed on each subarray, beginning with the largest gap size and progressively reducing it until it reaches 1. Lastly, the algorithm executes a final insertion sort on the complete array to ensure that all elements are correctly arranged.

The algorithm has the name of Donald Shell , who developed it and originally suggested it in 1959 . Now that we are familiar with the fundamentals of Shell sort , let's look at how to use C++ to implement it. There are three basic steps in the implementation:

• ✅ Using the gap sequence as a guide, divide the array into subarrays.
• ✅ Perform an insertion sort on each subarray.
• ✅ Execute a final insertion sort on the entire array after reducing the gap until it equals 1 .

Example:

Let's explore the C++ implementation of the Shell sort algorithm.

#include <iostream>
using namespace std;
 void shellSort(int arr[], int n) {
    // Calculate the gap sequence
    for (int gap = n/2; gap > 0; gap /= 2) {
        // Perform an insertion sort on each subarray
        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() {
    int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
shellSort(arr, n);
cout<< "Sorted array: ";
    for (int i = 0; i< n; i++) {
cout<<arr[i] << " ";
    }
    return 0;
}

Output:

The output of the above code is:

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

Explanation:

In the provided code, the initial step involves calculating the sequence of intervals based on the size of the array. Initially, a gap sequence of n/2 is established, which is successively divided by half until it reaches 1. Subsequently, beginning from this gap value and progressing towards the array's end, an insertion sort is executed on each subarray. In contrast to comparing adjacent elements, this insertion sort evaluates elements that are separated by specific gap intervals.

Conclusion

In this article, we explored the Shell sort algorithm and its implementation in the C++ programming language. Sorting an array with the efficient Shell sort technique involves comparing elements that are distant from each other rather than adjacent. The process initiates by dividing the array into smaller subarrays using a specific gap sequence, followed by applying an insertion sort to each subarray. The gap sequence is determined using the Knuth sequence formula, 3k - 1. As the algorithm iterates and reduces the gap size to 1, a final insertion sort is performed on the complete array.

This article's code snippet can be effortlessly modified to arrange arrays of various data types or in an alternative sequence (such as in a descending order). The Pratt and Tokuda progressions for generating gap sequences present two additional adaptations of the Shell sort technique that could be explored. Shell sort stands out as a favored sorting algorithm due to its simplicity and efficiency, making it a common selection for sorting small to medium-sized arrays in real-world scenarios.