Implementing Shell sort in Java

In this tutorial, we will implement shell sort in Java programming language. Shell sort is a sorting algorithm which does in place comparison. It is a generalization of insertion sort algorithm. This algorithm was invented by Donald shell.

This algorithm helps to sort elements which are far apart. While in insertion sort comparison happens only between adjacent elements, however, shell sort avoids comparing adjacent elements until the last steps. The last step of shell sort is ultimately insertion sort.

It improves insertion sort by comparison and exchange of elements that are far away.
Shell sort uses the increment sequence. It makes multiple passes over array and sort number of equally sized array using insertion sort.

The best-case time complexity of shell sort algorithm is O(n). Its worst-case complexity is O(nlogn).

Java Code: Shell Sort

import java.util.Arrays;
 public class ShellSort {
 public static void main(String[] args) {
 int[] arr = { 22, 53, 33, 12, 75, 65, 887, 125 };
 System.out.println("Before Sorting : ");
 System.out.println(Arrays.toString(arr));
 System.out.println("After Sorting : ");
 arr = shellsort(arr);
 System.out.println(Arrays.toString(arr));
 }
 private static int[] shellsort(int[] arr) {
 
 int h = 1;
 while (h <= arr.length / 3) {
 h = 3 * h + 1; 
 }

 while (h > 0) { 
 int i,len=arr.length;
 for (i = 0; i < len; i++)
 {
 
 int temp = arr[i];
 int j;
 
 for (j = i; j > h - 1 && arr[j - h] >= temp; j = j - h) {
 arr[j] = arr[j - h];
 }
 arr[j] = temp;
 }
 h = (h - 1) / 3;
 }
 return arr;
 }
 
}

Output:

Before Sorting : 
[22, 53, 33, 12, 75, 65, 887, 125]
After Sorting : 
[12, 22, 33, 53, 65, 75, 125, 887]

Hope you have enjoyed this tutorial on Shell sort. Feel free to drop your comments in the below comment section.

Also read,

• Implementing Heap Sort in Java
• Radix Sort In Java