C++ Program For Shell Sort In Data Structure

Shell Sort is an efficient in-place comparison sort that is an extension of Insertion Sort. It improves performance by allowing the exchange of items that are far apart.

In this article, you will learn how the Shell Sort algorithm works, understand its advantages, and implement it using C++.

Problem Statement

Efficiently sorting data is a fundamental requirement in computer science and various applications. While simple sorting algorithms like Bubble Sort or Insertion Sort are easy to understand, their performance degrades significantly with larger datasets, typically having a time complexity of O(n²). This makes them impractical for sorting large arrays of elements, where performance is critical.

Example

Consider an unsorted array of integers:

Unsorted Array: [12, 34, 54, 2, 3]

After applying Shell Sort, the array will be sorted in ascending order:

Sorted Array: [2, 3, 12, 34, 54]

Background & Knowledge Prerequisites

To understand Shell Sort, readers should have a basic grasp of:

• C++ Basics: Variables, data types, loops (for, while), conditional statements (if/else).
• Arrays: How to declare, initialize, and access elements in C++ arrays.
• Functions: Defining and calling functions.
• Basic Sorting Concepts: An understanding of simpler sorting algorithms, particularly Insertion Sort, is beneficial as Shell Sort builds upon its principles.

Use Cases or Case Studies

Shell Sort, while not as fast as algorithms like Quick Sort or Merge Sort in the worst case, finds practical application in several scenarios:

• Small to Medium-Sized Datasets: It performs well on datasets that are too large for O(n²) sorts but not large enough to warrant the overhead of more complex O(n log n) sorts.
• In-Place Sorting Requirement: As an in-place algorithm, it requires minimal additional memory, which is crucial in memory-constrained environments.
• Embedded Systems: Its relatively simple implementation and good average-case performance make it suitable for embedded systems where resources might be limited.
• Preliminary Sorting: It can be used as a preliminary sorting pass to partially sort an array, making subsequent passes with other algorithms (like Insertion Sort) more efficient.
• Educational Context: It serves as an excellent example of how optimizing a simple algorithm can lead to significant performance improvements.

Solution Approaches

Shell Sort improves upon Insertion Sort by comparing elements separated by a gap (or interval) and repeatedly reducing the gap size until it becomes 1. This process allows elements to move large distances towards their correct positions quickly.

Shell Sort Algorithm

Shell Sort works by repeatedly performing an Insertion Sort on subarrays of elements separated by a decreasing gap. It starts with a large gap and progressively reduces it until the gap is 1, at which point it becomes a standard Insertion Sort.

One-line summary: Shell Sort is an optimization of Insertion Sort that sorts elements at various decreasing intervals.

// Shell Sort Implementation in C++
#include <iostream>
#include <vector> // Using vector for dynamic arrays, common in modern C++
#include <numeric> // For std::iota if needed, not strictly for this simple example

// Function to print the elements of an array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Function to perform Shell Sort
void shellSort(std::vector<int>& arr) {
    int n = arr.size();

    // Start with a large gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is gap sorted
        for (int i = gap; i < n; i++) {
            // Store a[i] in temp and make a hole at position i
            int temp = arr[i];

            // Shift earlier gap-sorted elements up until the correct location for a[i] is found
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            // Put temp (the original a[i]) in its correct location
            arr[j] = temp;
        }
    }
}

int main() {
    // Step 1: Initialize an unsorted array
    std::vector<int> arr = {12, 34, 54, 2, 3};
    
    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(arr);

    // Step 3: Call the shellSort function to sort the array
    shellSort(arr);

    // Step 4: Print the sorted array
    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

Run

Sample Output:

Original array: 12 34 54 2 3 
Sorted array: 2 3 12 34 54

Stepwise explanation:

1. Initialize Gap: The algorithm begins by setting an initial gap value, typically n / 2 where n is the number of elements in the array. This gap determines how far apart elements are compared.
2. Outer Loop (Gap Reduction): The gap is repeatedly halved in each iteration (gap /= 2) until it becomes 0. When gap is 1, the algorithm essentially performs a standard Insertion Sort on the entire array.
3. Middle Loop (Gapped Insertion Sort): For each gap value, an inner loop iterates from i = gap to n-1. This loop treats elements arr[i], arr[i - gap], arr[i - 2*gap], ... as a sub-array that needs to be sorted using Insertion Sort logic.
4. Innermost Loop (Element Shifting): Inside the middle loop, arr[i] is taken as temp. Another loop (j) moves backwards from i in steps of gap. If arr[j - gap] is greater than temp, arr[j - gap] is shifted to arr[j]. This creates a "hole" for temp.
5. Placement: Once the correct position is found (where arr[j - gap] is no longer greater than temp or j becomes less than gap), temp is placed at arr[j].
6. Repeat: This process of gap-based insertion sort repeats for smaller and smaller gap values until the final gap of 1 ensures the entire array is fully sorted.

Conclusion

Shell Sort is a valuable sorting algorithm that offers a significant improvement over simple quadratic sorts like Insertion Sort. By introducing the concept of a gap, it allows elements to move quickly to their approximate final positions before a final, efficient Insertion Sort pass with gap = 1 completes the ordering. While its exact time complexity is still a subject of research and depends on the gap sequence used, it generally performs better than O(n²) sorts and is suitable for various real-world applications requiring an in-place, relatively fast sorting solution.

Summary

• Shell Sort is an in-place comparison sort that extends Insertion Sort.
• It sorts elements by comparing them at decreasing intervals (gaps).
• The algorithm starts with a large gap and progressively reduces it to 1.
• For each gap, it performs a gapped Insertion Sort on subarrays.
• It generally performs better than O(n²) sorts for practical inputs.
• Useful for small to medium datasets, memory-constrained environments, and as a preliminary sorting step.