Shell sort
Shell sort is a little modification in insertion sort, also called diminishing increment sort. Like in insertion sort we take a sorted part and an unsorted part of the array and gradually select the elements from the unsorted part and put it in the sorted part in the right position.
This is a good algorithm but under the hood, it requires a lot of comparisons and a lot of swaps. So to overcome this problem, Donald Shell made a little modification in this algorithm and named it shell sort(after his own name).
Shell sort is based on gap-based insertion sort. The gap keeps on decreasing and the array is sorted according to the gap. The gap is decreased on the basis of a sequence used for the array and the performance of the algorithm depends on the gap sequence we use.
Original gap sequence of shell sort: N/2, N/4, N/8, …… (N is the size of the array). But there are also some other gap sequences :
Knuth’s increments (kth gap is (3^k — 1) / 2) : 1, 4, 13, …., 3^k
Sedgewick’s gap sequence (kth gap is 4k+1+3.2k+1) : 1, 8, 23, 77, ….., 4k+1+3.2k+1
Pratts’s Gap sequence (kth gap is 2^i.3^j) : 1, 2, 3, 4, 6, 9,….
Papernov and Stasevich gap sequence: 1, 3, 5, 9,……..
Shell sort divides the array into subarrays, the elements for a subarray are selected from the input array which is k position distant(k is the gap). Suppose the gap is 3, the elements in the subarray will have a distance of 3 from each other. The subarray is sorted by performing insertion sort. Initially, the subarray has few elements but as the gap is decreased the elements in the subarray keeps on increasing. As the gap keeps on decreasing When the subarray has fewer elements, insertion sort is fast, and when the subarray has more elements(which are nearly sorted), then also insertion sort is fast( because when the list is sorted or nearly sorted insertion sort runs in linear time). So overall this shell sort has better complexity.
Let's suppose, an array has 12 elements. If we take the gap to be N/2 then the gap will be 6, each sublist having 2 elements. The first sublist will have element index 0 and 6, second 1 and 7, and more of the same which are 6 positions distant from each other (index is of the original array).
The gap not always needs to be N/2 apart, but we’ll take an example where we’ll take the gap sequence to be N/2, N/4, N/8, …..
So let's understand shell sort with an example. An array of size 10
We take gap= N/2, so at first, the gap is 5.
In pass 1, each subarray consists of 2 elements. The elements in the grey box are in a subarray, the first subarray has elements 18 and 34, so both of them are compared and then sorted. Similarly, the second subarray has elements 30 and 19, both of them compared and then sorted, and then for all the remaining subarray same thing is repeated.
And finally, after the first pass, we get a slightly sorted array.
Then in pass 2, the gap will become N/4 which is 2. So there will be 2 sublists each having 5 elements. The elements in the first subarray are at positions 0, 2, 4, 6, 8, and the second subarray elements are at positions 1, 3, 5,7,9. Again these subarrays will be sorted using insertion sort. After pass 2 the array becomes mostly sorted.
In pass 3 the gap is 1 which is sorted as a regular insertion sort. Since in this pass the array is mostly sorted it requires less swap, here only one swap is required to make the array sorted 12 and 10 are swapped and then the array becomes sorted.
After pass 3 the array is completely sorted.
C++ code for shell sort
#include<iostream>
using namespace std;
int main()
{
int n, i, j, temp, gap;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for (gap = n/2; gap > 0; gap = gap / 2)
{// Do a gapped insertion sort
// The first gap elements arr[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i = i + 1)
{// add arr[i] to the elements that have been gap sorted
// save arr[i] in temp and make a empty space at index i
int temp = arr[i];
// 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 = j - gap)
arr[j] = arr[j - gap];// put temp (the original arr[i]) in its correct position
arr[j] = temp;
}
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
Time Complexity
The time complexity of shell sort depends on the gap sequence used for the input array. If we take the original gap sequence, i.e. N/2 the complexity comes out to be O(n²), which is the worst case. But if we take a better gap sequence we can get a better time complexity and the algorithm may perform better. The best gap sequence is not known.
The best case is when the array is already sorted and its time complexity is O(n*log n).
Space complexity
Shell sort doesn't require any extra space during the working of the algorithm, so its space complexity is O(1) which is constant(linear).
