Lecture 357:- Shell Sort

Shell Sort is an in-place comparison-based sorting algorithm. It is an extension of the Insertion Sort algorithm and improves its time complexity by reducing the number of comparisons needed to move elements to their correct positions. Shell Sort works by sorting elements that are far apart first, and then progressively reducing the gap between elements to be compared until the entire array is sorted.

Here's how the Shell Sort algorithm works:

1. Choose a gap sequence (commonly used are powers of two or decreasing by half).
2. Start with the largest gap and perform an insertion sort on subarrays with elements that are gap positions apart.
3. Gradually reduce the gap size and repeat the insertion sort on subarrays until the gap becomes 1.
4. Finally, perform an insertion sort with gap 1, which is equivalent to the original Insertion Sort.

Here's the C++ implementation of Shell Sort:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Shell Sort function void shellSort(vector<int>& arr) {    int n = arr.size();    // Start with a large gap (half of the array size)    for (int gap = n / 2; gap > 0; gap /= 2) {        // Perform an insertion sort on subarrays with elements that are gap positions apart        for (int i = gap; i < n; i++) {            int temp = arr[i];            int j = i;            // Shift elements to the right until the correct position for temp is found            while (j >= gap && arr[j - gap] > temp) {                arr[j] = arr[j - gap];                j -= gap;            }            arr[j] = temp;        }    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "Original Array: ";    display(arr);    shellSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the shellSort function performs the Shell Sort algorithm to sort the input array. When you run this code, it will display the original array and then the sorted array after applying the Shell Sort algorithm.