Shell Sort
Shell sort, also known as Shell sort or Shell’s method, is an in-place comparison sort. It can be seen as a generalization of sorting by exchange by insertion sort. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shell sort is heavily dependent on the gap sequence it uses.
Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position. In shell sort, the list is sorted by breaking it down into a number of smaller subsists. It is not necessary that the lists need to be with contiguous elements. Instead, the shell sort technique uses increment i, which is also called “gap” and uses it to create a list of elements that are “i” elements apart.
General Algorithm
Thus, as shown in the picture, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.
Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.
How Shell Sort Works?
Let us consider the following example to have an idea of how shell sort works. For our example and ease of understanding, we take the interval i of 4. Make a virtual sub-list of all values located at the interval of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}
We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this –
Then, we take an interval of 2 and will compare the elements with gap 2
We compare and swap the values, if required, in the original array. After this step, the array should look like this –
Finally, we sort the rest of the array using an interval of value 1. Shell sort uses insertion sort to sort the array.
Following is the step-by-step depiction –
As seen above, after performing shell sort and merging the sorted subsists, we only required four moves to completely sort the list. Thus, we can see that we can significantly reduce the number of steps required to sort the array. The choice of increment to create sub-lists is a unique feature of shell sort.
Let us see the implementation of shell sort in C++ below.
#include <iostream>
using namespace std;
int shellSort(int arr[], int N)
{
for (int gap = N/2; gap > 0; gap /= 2)
{
for (int i = gap; i < N; i += 1)
{
int j;
for (j = i-gap; j >=0 ; j -= gap)
{
if(arr[j+gap]>arr[j]){
break;
}
else{
swap(arr[j+gap],arr[j]);
}
}
}
}
return 0;
}
int main()
{
int arr[] = {35,33,42,10,14,19,27,44};
int N = sizeof(arr)/sizeof(arr[0]);
cout << “Array to be sorted: \n”;
for (int i=0; i<N; i++)
cout << arr[i] << “ “;
shellSort(arr, N);
cout << “\nArray after shell sort: \n”;
for (int i=0; i<N; i++)
cout << arr[i] << “ “;
return 0;
}
Output:
Array to be sorted:
35 33 42 10 14 19 27 44
Array after shell sort:
10 14 19 27 33 35 42 44
We have used the same list that we used in the illustration and we can see that we begin initially by creating two sub-lists and then narrowing the gap further. Once sub-lists are created as per the gap specified, we sort each of the sublists. After all the sublists are sorted, we get the almost sorted list. Now this list can be sorted using the basic insertion sort which will take very few moves.
Applications:
Shell sort performs more operations and has a higher cache miss ratio than quicksort. Shell sort is, for example, used in the uClibc library. For similar reasons, in the past, Shell sort was used in the Linux kernel.
Time Complexity:
The time complexity of the above implementation of shell sort is O(n2). In the above implementation, the gap is reduced by half in every iteration. There are many other ways to reduce gaps which lead to better time complexity.
Gap Sequence:
The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yield a correct sort (as this makes the final pass an ordinary insertion sort); however, the properties of thus obtained versions of Shellsort may be very different. Too few gaps slow down the passes, and too many gaps produce an overhead. The most proposed gap sequences are.
• Shell’s original sequence: N/2, N/4, …, 1
• Hibbard’s increments: 1, 3, 7, …, 2k — 1;
• Knuth’s increments: 1, 4, 13, …, (3k — 1) / 2 ;
• Sedgewick’s increments: 1, 5, 19, 41, 109, ….
• Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,…
- Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81…
Conclusion:
Shell sort is the highly efficient algorithm that comes to an improvement over the insertion sort.
While insertion sort works by incrementing its elements by 1, shell sort uses the parameter “gap” to divide the array into sub-arrays whose elements are “gap” apart. Then we can sort the individual list using insertion sort to obtain the complete sorted array.
Shell sort performs faster than insertion sort and takes fewer moves to sort the array when compared to insertion sort.
