Introduction

Sorting algorithms are algorithms that rearrange a collection's members in a certain order. The order criteria can vary and it is typically user-defined.

In practice, the order criteria is provided to the algorithm as a method that compares two objects and returns:

0: If the compared entities are considered equal
1: if the first entity is considered greater than the second
-1: if the second entity is considered greater than the first

That being said, this is most effectively done when the collection we're sorting contains comparable objects - objects that implement the Comparable interface.

This article deals with one of the more advanced algorithms in particular – Shell Sort. But if you want to read more about some of the most common sorting algorithms, check out our article Sorting Algorithms in Java, which briefly touches on each.

Shell Sort

Most sorting algorithms compare elements, in our case numbers, which are near each other in some way. An example would be Bubble Sort, which compares adjacent elements and swaps them if needed. Shell Sort utilizes a completely different approach, comparing elements that are further apart in the beginning. Though, the further we sort, the closer they become.

The space between elements we are comparing (known as the gap) in the beginning can be given as one of the arguments when calling the algorithm. Shell Sort is considered to be a generalization of Insertion Sort, so it's useful to quickly draw a parallel between the two and recap Insertion Sort just in case.

Parallels with Insertion Sort

Insertion Sort places elements of a collection in their ordered place one at a time by selecting an element and comparing it with each element with a lower index. Once it finds the correct place for the current element, it's placed and the process repeats.

Here's a code snippet that should illustrate how Insertion Sort works. The whole collection is shifted to the right in the correct place to "free up" space for an element to be inserted.

public static void insertionSort(ArrayList<Integer> arr,int n) {
    int i, j, newValue;

    for (i = 1; i < n; i++) {
        newValue = arr.get(i);
        j = i;

        while (j > 0 && arr.get(j-1) > newValue) {
            arr.set(j,arr.get(j-1));
            j--;
        }
        arr.set(j,newValue);
    }
}

Shell Sort takes the insertion approach, but instead of assigning it its exact position, in each iteration it brings elements just closer to their place. Each pass will look a little more sorted, until it finally is.

To understand how this works, we must first explain what is a K-sorted array and what are its characteristics.

K-Sorted Array

Suppose A is an array of a size N. Array A is K-sorted if every element is, at most, K places away from its target position. In other words, for each i between 1 and N, the target place of A[i] is somewhere between i-K and 1+K in A.

For an unsorted, N-sized array, it is possible to K-sort it in O(N logK) time.

An important property of K-sorted arrays is that if K₁ sorted array is K₂-sorted, it stays K₁ sorted. This can easily be proven.

Case One

$$
K_{1} > K_{2}
$$

If A is K₁-sorted then every element from A is at most K₁ places away from its target position. If we then K₂-sort A then every element from A is at most K₂ places away from its target position. Since K₂ is smaller than K₁, if elements from A are at most K₂ places away from their target, then they must be closer than K₁ places from their target. That means that if A is K₂-sorted, it must be K₁-sorted.

Case Two

$$
K_{1} < K_{2}
$$

When A is K₁-sorted, if we K₂-sort it, no element will change place, because A already is K₂-sorted (explained in previous case). That means that it will also stay K₁-sorted.

Shell Sort Example

Unlike in Insertion Sort, where whenever we make a swap the collection is shifted to the right, in Shell Sort the elements whose positions we change get grouped together and then get sorted within the groups. After the groups are sorted, only then are they shifted, resulting is much less moving of the actual elements themselves.

A = [7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3]

Here, the number of elements is 11.

Now, we're supposed to choose a gap, between the elements we want to compare and then group:

$$
gap = [\frac{11}{2}] = 5.
$$

A: 7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3

Now, we make groups of numbers that are 5 elements apart (have 4 elements between them). The groups are (7, 29, 3), (13, 14), (18, 7), (22, 27), (8, 25).

Since N/2 is used for the initial gap value, the first group has 3 elements, and others have two elements each due to the fact our collection has an uneven number of elements.

A: 7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3

There are no elements in the first group with smaller index than 0, so we are starting from second index - whose value is 29. The next step is to compare 29 to all the elements in the group with smaller indexes.

7 < 29 is true so their places will not be swapped.

There are no other elements in the group with an index lower than 5, so we are finished with A[5].

The next number in the group is 3, whose original index is 10:

29 < 3 is false so they will be swapped:

A: 7, 13, 18, 22, 8, 3, 14, 7, 27, 25, 29

Now, the value of A[5] is 3. 29 must be on its ordered place in the group, because there is no element with greater index in that group. 3, on the other hand, might still be smaller than group members with lower indexes.

7 < 3 is false, so they will be swapped:

A: 3, 13, 18, 22, 8, 7, 14, 7, 27, 25, 29

There are no elements in A with a lower index than 10 that we haven't already compared to A[10]. All the members of the first group are now sorted.

The next group is (13, 14):

A: 3, 13, 18, 22, 8, 7, 14, 7, 27, 25, 29

It is easy to notice that if there are only two elements in the group, they are swapped only if the first one is bigger that the second one. The groups that are left now are (18, 7), (22, 27), and (8, 25) and the only group that will need swapping will be (18, 7):

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, 29

At this point there are no groups left to analyze, so the array is 5-sorted. Although looking better than before, it's still not quite finished.

Now, the gap is divided by two yet again:

$$
gap = [\frac{5}{2}] = 2
$$

Now, we make groups of elements that are just 2 elements apart, which means that there is only one element between them. These groups are (3, 7, 8, 14, 27, 29) and (13, 22, 7, 18, 25):

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, 29

Sorting when gap is 2 will be displayed on the 2-sorting of the second group.

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, 29

These two groups are sorted in the same way the previous groups were sorted, and we're left with:

A: 3, 7, 7, 13, 8, 18, 14, 22, 27, 25, 29

The last thing left to do is to 1-sort the array, which is, actually Insertion Sort.

Every member is compared to all other elements with smaller indexes. The important thing to notice here is that array is already 2-sorted, so it is only possible that elements on places i and i+1 are not ordered. Therefore, when 1-sorting, only elements next to each other can be swapped.

Implementation

With all of the above in mind, let's implement Shell Sort. The loop invariant in the main for loop is that the array is gap-sorted. The gap is halved on every iteration until it reaches 0. When it does, the array is sorted:

public static void shSort(ArrayList<Integer> arr,int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i+= 1) {

            int temp = arr.get(i);
            int j;
            for (j = i; j >= gap && arr.get(j-gap) > temp; j -= gap)
                arr.set(j,arr.get(j-gap));
            arr.set(j,temp);
        }
    }
}

The array and its size are given as arguments of the method and the loop gets executed log_n times.

The first nested for loop goes through groups of elements that are gap places apart. That loop gets executed n-gap times. The temp variable is necessary for swapping, as usual.

One of the conditions in the second nested for loop is that j > gap, because we are comparing an element to all members of the group with smaller indexes from right to left.

Due to this, the last number that will be observed will be the first member of the group. The second condition is that j-gap < temp. This means that the loop is being executed while there are elements with lower indexes that are bigger than arr[j].

The first one that is lower breaks the loop. Then, arr[j] gets moved to the index whose value it was smaller than. This loop repeats i/gap times.

Time Complexity

Let us now calculate the time complexity of Shell Sort. As was already mentioned, the first loop is executed log_n times.

The second loop starts with gap as the index, which is 2^k. Since in the third loop we subtract gap, that means that in the sum, i should be divided by gap:

\sum_{k = 0}^{\log_{2} n} \sum_{i = 2^{k - 1}}^{n - 1} \sum_{j = 0}^{\frac{i}{2^{k - 1}}} O (1) = \sum_{k = 0}^{\log_{2} n} \sum_{i = 2^{k - 1}}^{n - 1} \frac{i}{2^{k - 1}} = \sum_{k = 0}^{\log_{2} n} \frac{1}{2^{k - 1}} \sum_{i = 2^{k - 1}}^{n - 1} i = \sum_{k = 0}^{\log_{2} n} \frac{1}{2^{k - 1}} * \frac{(n - 1 - 2^{k - 1}) * (n - 2^{k - 1})}{2} = \sum_{k = 0}^{\log_{2} n} \frac{(n - 1 - 2^{k - 1}) * (n - 2^{k - 1})}{\frac{1}{2^{k}}} = \sum_{k = 0}^{\log_{2} n} \frac{n^{2} - n - 2 * n 2^{k - 1} + 2^{k - 1} + 2^{2 k - 2}}{\frac{1}{2^{k}}} = \sum_{k = 0}^{\log_{2} n} \frac{n^{2}}{2^{k}} - \frac{n}{2^{k}} - n + \frac{1}{2} + 2^{k - 2} = n^{2} \sum_{k = 0}^{\log_{2} n} \frac{1}{2^{k}} - n \sum_{k = 0}^{\log_{2} n} \frac{1}{2^{k}} + (\frac{1}{2} - n) \log_{2} n + \sum_{k = 0}^{\log_{2} n} 2^{k - 2} = n^{2} \frac{(\frac{1}{2})^{\log_{2} n + 1} - 1}{\frac{1}{2} - 1} - n \frac{(\frac{1}{2})^{\log_{2} n + 1}}{\frac{1}{2} - 1} + \frac{1}{4} * \frac{2^{\log_{2} n + 1} - 1}{2 - 1} + o (n \log n) = (2 n^{2} - n) (1 - \frac{1}{2 n}) + \frac{1}{4} (2 n - 1) + o (n \log n) = 2 n^{2} - \frac{3 n}{2} + \frac{1}{4} + o (n \log n) = O (n^{2})

*Scroll to view*

This all brings the time complexity to O(n logn). Here, we assumed the fact that gap is set to n/2.

If the gap is set differently, the time complexity is different. Here, you can read more details on time complexity of Shell Sort depending on the choice of the gap variable.

Conclusion

Shell Sort compares elements that are further apart in the beginning, though, the further we sort, the closer they become resulting in an array that's a bit more sorted after each iteration.

Shell Sort performs better than Insertion Sort but it has a bigger cache miss ratio than Quick Sort.

If you want to read more about most common sorting algorithms, check out our article on Sorting Algorithms in Java.

Dunja Spasić

Recently published

Shell Sort in Java