# C++ Program to Implement Shell Sort

C++ Program to Implement Shell Sort

shell sort is basically an Insertion Sort variant. In the insertion sort, we only transfer elements ahead of one location. Many movements are involved when an item has to be pushed far ahead. The idea behind shell sort is to allow the exchange of far-flung items. In shell sort, for a great value of h, we make the array h-sorted. We hold the value of h decreasing until it is 1. If all sublists of any h'th element are sorted, an array is said to be h-sorted.

The complexity of the Shell Sort Technique

• Time Complexity: O(n log n) for the best-case scenario, and relies heavily on the distance series also in other cases.
• Space Complexity: O(1)

Input:- The unsorted list: 25, 4, 87, 94, 11, 30, 210, 200, 51, 99, 10

Output:- Array after Sorting: 4, 10, 11, 25, 30, 51, 87, 94, 99, 200, 210

### Algorithm

`ShellSort(array, size)`

Input: A data collection, and the overall number in the array

Output: The sorted Array

`shell_sort (A, N)where A – list to be sorted; N – gap_size`
`set gap_size = N, flag = 1while gap_size > 1 or flag = 1, repeatbeginset flag = 0set gap_size = (gap_size + 1)/2endfor i = 0 to i< (N-gap_size) repeatbeginif A[i + gap_size] > A[i]swap A[i + gap_size], A[i]set flag = 0endend`

Thus, we first set N in the above algorithm, which is the gap to sort the array A using shell sort. In the next step, we divide the whole array into sub-arrays using the distance. Then we sort each of the sub-arrays in the next step so that we get a sorted array at the end of the loop.

Simple Example Code of shell sort

```// Program to implementation of Shell Sort in C++
#include <iostream>
using namespace std;
int shellSort(int array[], int p)
{
for (int gap = p/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// keep adding one more element until the entire array is
// gap sorted
for (int l = gap; l < p; l += 1)
{
// add a[l] to the elements that have been gap sorted
// save a[l] in temp and make a hole at position l
int temp = array[l];
// shift earlier gap-sorted elements up until the correct
// location for a[l] is found
int j;
for (j = l; j >= gap && array[j - gap] > temp; j -= gap)
array[j] = array[j - gap];
//  put temp (the original a[l]) in its correct location
array[j] = temp;
}
}
return 0;
}
void printArray(int array[], int p)
{
for (int l=0; l<p; l++)
cout << array[l] << " ";
}
int main()
{
int array[] = {70, 5, 3, 16, 25, 77, 110, 40, 21}, l;
int p = sizeof(array)/sizeof(array);
cout << "Array before sorting: \n";
printArray(array, p);
shellSort(array, p);
cout << "\nArray after sorting: \n";
printArray(array, p);
return 0;
}```

Output: