Shell Sort in Java

Introduction

This tutorial explains the Shell Sort Algorithm with an example list of 8 numbers. It then provides the Java implementation of Shell Sort Algorithm and explains its Big Oh complexity.

What is Shell Sort

Shell sort is an in-place sorting algorithm which improves upon Insertion SortClick to read: Insertion Sort. It is named after Donald Shell, who published it in 1959. Insertion sort moves an item only one place at a time, so an item which is far away from its correct position needs many moves to get there. Shell sort fixes this by first sorting items which are far apart from each other, so that such items can move a long distance in a single step.

The distance between the items being compared is called the gap. Shell sort starts with a large gap, and does an insertion sort of the items which are gap places apart. It then reduces the gap and repeats. With every pass the list becomes more nearly sorted. The last pass is done with a gap of 1, which is an ordinary insertion sort. By that time very few items are out of place, so the last pass needs very few moves.

Shell Sort Working Explained

Lets understand the working of Shell Sort using an example. Lets say the list to be sorted is [35, 33, 42, 10, 14, 19, 27, 44]. We will start with a gap equal to half the size of the list, i.e. 4, and halve the gap with every pass.
First pass with a gap of 4
Items which are 4 places apart form a group, so the list has 4 groups of 2 items each - (35, 14), (33, 19), (42, 27) and (10, 44). Each group is sorted by insertion sort. 14 is smaller than 35, so they are swapped. Similarly 19 is swapped with 33, and 27 with 42. 10 and 44 are already in order. List has now become [14, 19, 27, 10, 35, 33, 42, 44]. The smaller items have moved 4 places to the left in a single step.

The first pass of shell sort with a gap of 4 on the list 35, 33, 42, 10, 14, 19, 27, 44 - the items 4 places apart form the groups 35 and 14, 33 and 19, 42 and 27, 10 and 44; sorting each group swaps the first three pairs and gives 14, 19, 27, 10, 35, 33, 42, 44 Second pass with a gap of 2
The gap is now 2, so there are 2 groups of 4 items each. The items at the even positions are (14, 27, 35, 42), which are already in order. The items at the odd positions are (19, 10, 33, 44). Sorting them gives (10, 19, 33, 44), i.e. 10 moves 2 places to the left and 19 moves 2 places to the right. List has now become [14, 10, 27, 19, 35, 33, 42, 44].

Third pass with a gap of 1
With a gap of 1 the whole list is one group, and this pass is an ordinary insertion sort. But the list is now nearly sorted, and only 3 small moves are needed - 10 is placed before 14, 19 before 27, and 33 before 35. The list has now become [10, 14, 19, 27, 33, 35, 42, 44], which is the sorted list.

Shell Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class ShellSort {
  static int intArray[] = { 35, 33, 42, 10, 14, 19, 27, 44 };
  public static void doSort() {
    for (int gap = intArray.length / 2; gap > 0; gap = gap / 2) {
      for (int outer = gap; outer < intArray.length; outer++) {
        int temp = intArray[outer];
        int inner = outer;
        while (inner >= gap && intArray[inner - gap] > temp) {
          intArray[inner] = intArray[inner - gap];
          inner = inner - gap;
        }//inner loop ends
        intArray[inner] = temp;
      }//outer loop ends
    }//gap loop ends
  }
  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }
  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 35 33 42 10 14 19 27 44
Array After Sorting -> 10 14 19 27 33 35 42 44

Explanation of the code

  • The doSort() method in the above java program holds the sorting logic.
  • There are 3 loops. The loop with the counter gap represents the passes. It starts with half the length of the list and halves the gap after every pass, until the gap becomes 0.
  • The loop with the counter outer picks the items one by one, starting from the item at index gap. Every picked item is inserted into its correct place among the items of its group which are before it, i.e. the items gap, 2*gap, ... places to its left.
  • The while loop with the counter inner does this insertion. The picked item is kept in temp. As long as the item gap places to the left is greater than temp, that item is moved gap places to the right. When the loop ends, temp is placed in the position which has been freed.
  • Except for the steps of size gap instead of 1, the two inner loops are the same as in insertion sort. With a gap of 1, they are exactly an insertion sort.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.

Big Oh Complexity of Shell Sort Algorithm

The complexity of shell sort depends on the sequence of gaps used, and working it out exactly is difficult. With the gaps used above, which halve with every pass (n/2, n/4, ... 1), there are inputs for which the passes with the larger gaps do not help, and the worst case complexity of shell sort with this gap sequence is O(n2), the same as insertion sort. Better gap sequences improve the worst case. For example, the sequence 1, 4, 13, 40, ... (each gap is 3 times the previous one plus 1) gives a worst case of O(n3/2).

In practice shell sort is much faster than insertion sort on medium-sized lists, and it sorts in-place without any extra space. It is not a stable sort, as items with equal values can be moved past each other while sorting the groups.

Summary

In this tutorial on shell sort algorithm in java we understood how the algorithm improves insertion sort by first sorting items which are a gap apart, went through a step-by-step walkthrough of sorting an 8-number list with gaps of 4, 2 and 1, saw the java code for implementing shell sort along with its explanation, and finally understood its Big Oh complexity.