Shell Sort in C++

How to Implement Shell Sort in C++ (With Code Example and Pseudocode)

Shell Sort is a fast, comparison-based sorting algorithm that improves upon insertion sort by allowing comparisons between elements that are far apart. This C++ implementation follows the same principles as Shell Sort in Python but leverages the speed and efficiency of C++. In this article, we’ll walk you through how Shell Sort works, provide pseudocode, show a C++ implementation, and include a detailed step-by-step walkthrough with a larger array example.

For comparisons with other sorting algorithms, pros and cons, and additional details, please refer to the How to Do Shell Sort in Python article.

---

What is Shell Sort?

Shell Sort is an enhanced version of insertion sort that allows elements to move faster toward their correct positions by first comparing elements that are far apart (based on a gap). As the gap shrinks, the algorithm refines the sort until the gap is 1, at which point it performs a final insertion sort.

Shell Sort is efficient for medium-sized datasets and relies heavily on the choice of the gap sequence.

---

How Shell Sort Works

1. Initialize a gap: The gap is usually set to half the size of the array.
2. Compare elements separated by the gap: Perform an insertion sort on elements separated by the gap.
3. Reduce the gap: After each pass, reduce the gap and repeat the process.
4. Perform final insertion sort: Once the gap reaches 1, the algorithm finishes with a regular insertion sort.

Shell Sort Pseudocode

Here’s the pseudocode for Shell Sort, adapted for C++:

ShellSort(array, n):
    gap = n // 2  # Initialize the gap

    while gap > 0:
        for i = gap to n - 1:
            temp = array[i]
            j = i

            # Perform insertion sort for the current gap
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]  # Shift larger elements to the right
                j = j - gap

            array[j] = temp  # Insert temp in its correct location

        gap = gap // 2  # Reduce the gap

---

Shell Sort in C++ (Code Example)

Here’s a C++ implementation of Shell Sort using the same logic as the pseudocode above:

#include <iostream>
using namespace std;

// Function to implement Shell Sort
void shellSort(int arr[], int n) {
    // Start with a gap of n/2, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform insertion sort with the current gap
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            // Shift elements that are gap apart
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            // Place the temp element in its correct position
            arr[j] = temp;
        }
    }
}

// Utility function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 19 22 63 105 2 78 54 92 10 45 72 8 18 66 3
Sorted array: 2 3 8 10 18 19 22 45 54 63 66 72 78 92 105

---

Step-by-Step Walkthrough of Shell Sort

Let’s walk through how Shell Sort works using the larger array [19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3].

Step 1: Initialize the Gap Sequence

• The initial gap is calculated as half of the array length (n // 2), which is 15 // 2 = 7.

Initial gap: 7

Step 2: Perform Insertion Sort for Elements with Gap 7

• We now compare and swap elements that are 7 positions apart.

Array before sorting:

[19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3]

• Compare arr[0] (19) and arr[7] (92): No swap.
• Compare arr[1] (22) and arr[8] (10): Swap → [19, 10, 63, 105, 2, 78, 54, 92, 22, 45, 72, 8, 18, 66, 3].
• Compare arr[2] (63) and arr[9] (45): Swap → [19, 10, 45, 105, 2, 78, 54, 92, 22, 63, 72, 8, 18, 66, 3].
• Compare arr[3] (105) and arr[10] (72): Swap → [19, 10, 45, 72, 2, 78, 54, 92, 22, 63, 105, 8, 18, 66, 3].
• Compare arr[4] (2) and arr[11] (8): No swap.
• Compare arr[5] (78) and arr[12] (18): Swap → [19, 10, 45, 72, 2, 18, 54, 92, 22, 63, 105, 8, 78, 66, 3].
• Compare arr[6] (54) and arr[13] (66): No swap.
• Compare arr[7] (92) and arr[14] (3): Swap → [19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92].

Array after first pass (gap 7):

[19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92]

Step 3: Reduce the Gap

• We reduce the gap by dividing it by 2: 7 // 2 = 3.

New gap: 3

Step 4: Perform Insertion Sort with Gap 3

• Now we compare and swap elements that are 3 positions apart.
• Compare arr[0] (19) and arr[3] (72): No swap.
• Compare arr[1] (10) and arr[4] (2): Swap → [19, 2, 45, 72, 10, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[2] (45) and arr[5] (18): Swap → [19, 2, 18, 72, 10, 45, 54, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[3] (72) and arr[6] (54): Swap → [19, 2, 18, 54, 10, 45, 72, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[4] (10) and arr[7] (3): Swap → [19, 2, 18, 54, 3, 45, 72, 10, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[5] (45) and arr[8] (22): Swap → [19, 2, 18, 54, 3, 22, 72, 10, 45, 63, 105, 8, 78, 66, 92].
• Compare arr[6] (72) and arr[9] (63): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 45, 72, 105, 8, 78, 66, 92].
• Compare arr[7] (10) and arr[10] (105): No swap.
• Compare arr[8] (45) and arr[11] (8): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 105, 45, 78, 66, 92].
• Compare arr[9] (72) and arr[12] (78): No swap.
• Compare arr[10] (105) and arr[13] (66): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92].
• Compare arr[11] (45) and arr[14] (92): No swap.

Array after second pass (gap 3):

[19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92]

Step 5: Reduce the Gap to 1 (Final Insertion Sort Pass)

• Now, reduce the gap to 1 (regular insertion sort).

New gap: 1

• Perform adjacent comparisons and swaps as necessary to complete the sorting.

Array after final pass (gap 1):

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

Final Sorted Array:

After completing all gap reductions, the array is fully sorted:

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

Advantages of Shell Sort

• Improved performance over basic sorting algorithms like insertion and bubble sort.
• In-place sorting with O(1) space complexity, making it memory-efficient.
• Easy to implement and adapt to various gap sequences.

Limitations of Shell Sort

• Performance depends on the gap sequence, and poor choices can lead to suboptimal performance.
• Not stable, meaning it may not preserve the relative order of equal elements.
• Generally slower than more advanced algorithms like quicksort and merge sort on large datasets.

For smaller and medium-sized datasets where memory usage is a concern, Shell Sort strikes a good balance between simplicity and efficiency.

Conclusion

Shell Sort is a versatile and efficient sorting algorithm that builds on insertion sort by first sorting far apart elements, gradually reducing the gap until a final insertion sort is performed. It is particularly well-suited for medium-sized datasets, offering better performance than bubble or insertion sort, especially when the data is unsorted. Its simplicity and in-place sorting (O(1) space complexity) make it a good option when memory efficiency is critical.

Congratulations on reading to the end of this tutorial!

For more details on Shell Sort’s comparison with other algorithms, its advantages and limitations, and further explanations, please refer to the How To Do Shell Sort in Python article. This version covers Shell Sort in Python and compares it to algorithms like quick sort, merge sort, insertion sort, and more.

For further reading on sorting algorithms in C++, go to the articles:

• How To Do Heap Sort in C++
• How To Do Quick Sort in C++
• How To Do Selection Sort in C++
• How To Do Merge Sort in C++
• How To Do Comb Sort in C++
• How To Do Insertion Sort in C++
• How To Do Radix Sort in C++
• How To Do Bucket Sort in C++

Have fun and happy researching!