Shell Sort Java Program

This tutorial shows how to write Shell sort program in Java. Shell sort is also an in place sorting algorithm like Bubble sort, Selection sort but it is faster than these algorithms.

Shell sort algorithm

Shell sort is based on Insertion sort and it improves on it to make sorting more efficient. In insertion sort if a small element is farther on the right that will require shifting a lot of element to bring it at its proper place on the left.

In Shell sort insertion sorting is done on elements at certain interval. Once these elements are sorted interval is reduced and sorting is done on elements at the new interval, once those elements are sorted interval is further reduced and so on. This process is repeated until the interval between elements is 1. At that time adjacent elements are compared and shell sort effectively becomes insertion sort in that iteration.

By the time, interval becomes 1 and adjacent elements are compared array is already 'almost sorted' because of the incremental sorting done in intervals, which means shifting of elements to extreme ends won't be required. Note that for almost sorted elements insertion sort has the complexity of O(N) rather than O(N²).

Shell sort interval sequence

In shell sort you start with a gap interval and that interval is repeatedly reduced until it becomes 1. Most common way of calculating interval sequence for shell sort is known as Knuth interval sequence. Values for Knuth interval sequence are generated using the following expression-

interval = (interval * 3) + 1;

Where the initial value of interval is 1.

To reduce the interval following formula is used, which is the reverse of the above formula-

interval = (interval - 1)/3;

Shell sort Java Program

public class ShellSort {
  public static void main(String[] args) {
    int[] arr = {10, 52, 23, 32, 3, 56, 87, 12, 37, 91, 34, 78};
    System.out.println("Input array- " + Arrays.toString(arr));
    int[] sortedArray = shellSort(arr);
    System.out.println("Sorted array after shell sort- " + Arrays.toString(sortedArray));
  }
	
  private static int[] shellSort(int[] arr){
    int interval = 1;
    int temp;
    // interval calculation using Knuth's interval sequence
    while(interval <= arr.length/3){
      interval = (interval * 3) + 1;
    }
    while(interval > 0){    
      for(int i = interval; i < arr.length; i++){
        temp = arr[i];
        int j;                
        for(j = i; j > interval - 1 && arr[j-interval] >= temp; j=j-interval){
          arr[j] = arr[j - interval];                    
        }
        arr[j] = temp;
      }
      // reduce interval 
      interval = (interval - 1)/3;
    }
    return arr;
  }
}

Output

Input array- [10, 52, 23, 32, 3, 56, 87, 12, 37, 91, 34, 78]
Sorted array after shell sort- [3, 10, 12, 23, 32, 34, 37, 52, 56, 78, 87, 91]

Shell sort time and space complexity

Average time complexity of shell sort is considered as O(N^3/2).

Shell sort is an in place sorting algorithm so no auxiliary space is needed. Therefore space complexity of Shell sort is O(1).

That's all for the topic Shell Sort Java Program. If something is missing or you have something to share about the topic please write a comment.

---

You may also like

• Bucket Sort Java Program
• Convert LocalDateTime to OffsetDateTime in Java
• Generating PDF in Java Using PDFBox Tutorial
• do-while loop in Java With Examples
• Constructor Overloading in Java
• How to Synchronize Java ArrayList
• Spring Dependency Injection With Examples
• tempfile Module in Python - Create Temporary File and Directory