Shell Sort Algorithm with EXAMPLE

What is Shell Sort

Shell’s method, or Shell sort in Data structure, is an efficient in-place comparison sort algorithm. It is named after Donald Shell when he proposed the initial idea back in 1959. Shell sort is a generalized extension of the insertion sort algorithm.

The fundamental idea of this sorting algorithm is to group the elements that are far apart and sort them accordingly. Then gradually decrease the gap between them. Shell sort overcomes the average case time complexity of insertion sort by comparing and exchanging elements that are far away.

This gap, known as the interval, is reduced according to some optimal gap sequences. The running time of shell sort is also dependent on these sequences. There are several gap sequences, such as Shell’s original sequence, Knuth’s formula, Hibbard’s increments, etc. Shell’s original gap sequence is – n/2, n/4, n/8, ……….1

Shell Sort Algorithm

The steps or procedure for the shell sort algorithm is as follows-

Step 1) Initialize the interval value, h = n/2. (In this example, n is the size of the array)

Step 2) Put all the elements within a distance of the interval h in a sub-list.

Step 3) Sort those sub-lists using insertion sort.

Step 4) Set new interval, h=h/2.

Step 5) If h>0, go to step 2. Else go to step 6.

Step 6) The resultant output will be the sorted array.

How Shell Sort Works

In insertion sort, elements are moved by only one position at a time. On the contrary, shell sort divides the array into smaller pieces based on the interval value and executes insertion sort on those pieces.

Gradually, the interval value decreases, and the divided pieces’ size increases. As the pieces are individually sorted beforehand, merging those pieces requires fewer steps than the insertion sort.

The following GIF shows a demonstration of shell sort. In this demo, the red and the blue indicated value is compared and swapped based on insertion sort. Then the interval decreases, and shell sort initiates insertion sort in that almost sorted data.

Working of Shell Sort Algorithm

Let’s see a following example of a shell sort algorithm. In this example, we will sort the following array using shell sort:

Step 1) Here, the array size is 8. Thus, the interval value will be h = 8/2 or 4.

Step 2) Now, we will store all the elements at a distance of 4. For our case, the sublists are- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Step 3) Now, those sublists will be sorted using insertion sort, where a temporary variable is used to compare both numbers and sort accordingly.

The array would be like the following after swapping operations-

Step 4) Now, we will decrease the initial value of the interval. The new interval will be h=h/2 or 4/2 or 2.

Step 5) As 2>0, we will go to step 2 to store all the elements at a distance of 2. For this time, the sublists are-

{1, 5, 8, 7}, {4, 2, 6, 3}

Then these sublists will be sorted using insertion sort. After comparing and swapping the first sublist, the array would be the following.

After sorting the second sublist, the original array will be:

Then again, the interval will be decreased. Now the interval will be h=h/2 or 2/1 or 1. Hence we will use the insertion sort algorithm to sort the modified array.

Following is the step-by-step procedural depiction of insertion sort.

The interval is again divided by 2. By this time, the interval becomes 0. So we go to step 6.

Step 6) As the interval is 0, the array is sorted by this time. The sorted array is-

Pseudo-Code

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

Shell Sort Program in C/C++

Input:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Output:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Sort Example in Python

Input:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Output:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Applications of Shell Sort

Here are important applications of Shell Sort:

• Shell sort is used in the Linux kernel because it does not use a call stack.
• uClibc library uses Shell sort.
• bzip2 compressor uses Shell sort to stop exceeding recursion.

Advantages & Disadvantages of Shell Sort

Advantages	Disadvantages
No stack call is required.	Not efficient for huge array sizes.
Easy implementation.	Inefficient for widely spread elements.
Efficient for less widely spaced elements.

Shell Sort Complexity Analysis

Time Complexity of Shell Sort

The time complexity of shell sort algorithm is O(n^2). The reasoning is as follows:

For the best-case scenario, the total amount of tests for all intervals when the array was previously arranged equal log n. Thus the complexity would be O(n*log n).

For the worst-case scenario, let’s consider the array consists in such a way that the elements require the highest number of comparisons. Then all elements will not be compared and switched until the last iteration. Therefore, the total comparisons required for the final increment is O(n^2).

In conclusion, the time complexities would be

1. Best case complexity: O(n*log n)
2. Average case complexity: O(n*log n)
3. Worst case complexity: O(n^2)

The running time complexity of shell sort heavily depends on the gap increment sequences used. However, the best increment sequence for shell sort is still unknown.

Shell Sort Space Complexity

In this comparison sort, we don’t need any additional auxiliary space. Thus the space complexity of this sort of algorithm is O(1).