Shell Sort

Definition:​

Shell sort is an extension of insertion sort that allows the exchange of far-apart elements to move elements towards their correct position faster. It starts by sorting pairs of elements far apart, then progressively reduces the gap between elements to be compared. This makes Shell sort more efficient than insertion sort, especially for larger datasets.

Video Explanation​

Watch

Characteristics:​

• Gap-based Sorting:

  • The core idea of Shell sort is to first sort elements that are far apart, using a sequence of gaps that reduces until a final insertion sort is performed when the gap is 1.

• In-Place Sorting:

  • Shell sort is an in-place algorithm, which means it requires no extra memory besides the input array itself.

• Unstable:

  • Shell sort is an unstable sorting algorithm because it can swap elements that are far apart, which may disrupt the relative order of equal elements.

• Gap Sequence:

  • The choice of gap sequence is crucial to the performance of Shell sort. Common sequences include the original gap sequence (n/2, n/4, ..., 1), Hibbard's sequence, and Sedgewick's sequence, among others.

Time Complexity:​

• Best Case: O(n log n)
  With an optimal gap sequence, Shell sort can approach O(n log n) in the best case.

• Average Case: O(n log² n)
  The average-case complexity of Shell sort is better than that of many simple quadratic sorting algorithms like insertion sort or bubble sort, but it depends heavily on the gap sequence.

• Worst Case: O(n²)
  In the worst case, with poor gap choices, Shell sort can degrade to quadratic time complexity.

Space Complexity:​

• Space Complexity: O(1)
  Shell sort is an in-place sorting algorithm, meaning it requires a constant amount of extra memory.

C++ Implementation:​

#include <iostream>
using namespace std;

// Function to perform shell sort
void shellSort(int arr[], int size) {
    // Start with a large gap, then reduce the gap
    for (int gap = size / 2; gap > 0; gap /= 2) {
        // Perform a gapped insertion sort for this gap size
        for (int i = gap; i < size; i++) {
            int temp = arr[i];
            int j;

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

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

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    shellSort(arr, size);

    cout << "Sorted array: \n";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation:​

1. Gap Selection:

   • Shell sort begins by choosing a large gap (half the size of the array) and performs a "gapped" insertion sort, comparing and swapping elements far apart. The gap is progressively reduced, and finally, when the gap becomes 1, the array is fully sorted using a regular insertion sort.

2. Performance Improvement:

   • Sorting with larger gaps allows elements to move towards their correct position faster, reducing the number of swaps needed during the final insertion sort pass. This significantly improves performance compared to a standard insertion sort.

Gap Sequences:​

• Shell's Original Sequence: The gap is initially set to half the array size and is halved each time (n/2, n/4, ..., 1).
• Hibbard's Sequence: Uses gaps of the form (1, 3, 7, 15, 31, ..., 2ⁿ−1), which provides better performance in practice.
• Sedgewick's Sequence: More complex, but provides excellent performance for larger arrays.

Summary:​

Shell sort is a highly efficient general-purpose comparison-based sorting algorithm that improves upon insertion sort by first comparing elements far apart. By reducing the gap over iterations, it minimizes the number of comparisons and swaps required. With its average-case time complexity of O(n log² n), Shell sort performs significantly better than simple quadratic algorithms like bubble or insertion sort, making it suitable for moderate-sized datasets. However, the performance depends heavily on the choice of the gap sequence.