Shell Sort in C++

Shell Sort is an in-place comparison sorting algorithm that is used to sort elements in an array. It is a relatively simple algorithm, but is still effective for a variety of sorting scenarios. This article will cover how the Shell Sort algorithm works, its time and space complexity, and how to implement it in C++.

What is Shell Sort? 

Shell Sort is a sorting algorithm that was created by Donald Shell in 1959. It is an improvement on the Insertion Sort algorithm and works by comparing elements that are a certain distance apart, called the gap, instead of just adjacent elements. This makes the algorithm more efficient than Insertion Sort, as it can move elements further down the array in fewer comparisons.

How Does Shell Sort Work? 

Shell Sort works by comparing elements that are a certain distance apart in the array – this distance is known as the gap. It starts by comparing elements that are gap elements apart, then reduces the gap size, and repeats the process. The gap size is reduced until the gap is equal to one, at which point the array is sorted.

Shell Sort works by comparing elements in the array that are a certain distance apart, known as the gap. The gap is initially set to the length of the array divided by two. It then compares elements that are gap elements apart, and swaps them if they are in the wrong order. After comparing elements that are gap elements apart, the gap size is reduced to the floor of the length of the array divided by two, and the process is repeated. This process continues until the gap is equal to one, at which point the array is sorted.

Time Complexity of Shell Sort 

The time complexity of Shell Sort depends on the gap size used. The best-case time complexity of Shell Sort is O(n log2 n), and the worst-case time complexity is O(n2). The average time complexity of Shell Sort is O(n1.5).

Space Complexity of Shell Sort 

The space complexity of Shell Sort is O(1), as it is an in-place algorithm. This means that it does not require any additional memory to sort the array.

Implementing Shell Sort in C++ 

The following code snippet shows how to implement Shell Sort in C++:

// Function to sort an array using Shell Sort 
void shellSort(int arr[], int n) 
{ 
    // Start with a big 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 += 1) 
        { 
            // add a[i] to the elements that have been gap sorted 
            // save 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; 
        } 
    } 
} 

Conclusion

In conclusion, Shell Sort is an in-place comparison sorting algorithm that is used to sort elements in an array. It works by comparing elements that are a certain distance apart and swapping them if they are in the wrong order. The time complexity of Shell Sort depends on the gap size used, with the best-case time complexity of O(n log2 n), the worst-case time complexity of O(n2), and the average time complexity of O(n1.5). The space complexity of Shell Sort is O(1), as it is an in-place algorithm. The code snippet provided shows how to implement Shell Sort in C++.

Exercises

// Function to sort an array using Shell Sort 
void shellSort(int arr[], int n) 
{ 
    // Start with a big 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 += 1) 
        { 
            // add a[i] to the elements that have been gap sorted 
            // save 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; 
        } 
    } 
} 

// Function to generate an array of random integers of size n 
int* generateRandomArray(int n) 
{ 
    // Create an array of size n 
    int* arr = new int[n]; 
  
    // Fill the array with random integers 
    for (int i = 0; i < n; i++) 
        arr[i] = rand() % 100; 
  
    // Return the array 
    return arr; 
} 

#include <iostream> 
  
// Function to sort an array using Shell Sort 
void shellSort(int arr[], int n) 
{ 
    // Start with a big 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 += 1) 
        { 
            // add a[i] to the elements that have been gap sorted 
            // save 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; 
        } 
    } 
} 
  
// Function to generate an array of random integers of size n 
int* generateRandomArray(int n) 
{ 
    // Create an array of size n 
    int* arr = new int[n]; 
  
    // Fill the array with random integers 
    for (int i = 0; i < n; i++) 
        arr[i] = rand() % 100; 
  
    // Return the array 
    return arr; 
} 
  
// Function to print an array 
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        std::cout << arr[i] << " "; 
    std::cout << std::endl; 
} 
  
// Main function 
int main() 
{ 
    // Generate an array of random integers 
    int n = 10; 
    int* arr = generateRandomArray(n); 
  
    // Print the array 
    std::cout << "Original Array: \n"; 
    printArray(arr, n); 
  
    // Sort the array 
    shellSort(arr, n); 
  
    // Print the sorted array 
    std::cout << "\nSorted Array: \n"; 
    printArray(arr, n); 
  
    return 0; 
}