Shell Sort in Java

In this tutorial, we will learn how to implement Shell Sort in java. First, we will start by understanding the Shell Sort algorithm.

• Sorting Algorithms in Java

Shell Sort Algorithm

Shell sort is an in-place comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.

In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

Time Complexity of Shell Sort:

• Best case:  0(nlogn)
• Average case:  0(n(logn)^2)
• Worst case:  0(n(logn)^2)

Before we begin, you need to have an idea of the following:

• Methods in java
• for loop in java
• while loop in java

---

Implementation of Shell sort in java

import java.util.Arrays;

public class ShellSortJava
{
  public static void main(String[] args)
  {
    int[] arr = { 23, 12, 89, 145, 10, 8, 333, 1, 70, 67 };

    System.out.println("Array Before Sorting : ");
    System.out.println(Arrays.toString(arr));

    System.out.println("Array After Shell Sorting : ");
    arr = shellsort(arr);
    System.out.println(Arrays.toString(arr));
  }

  private static int[] shellsort(int[] array)
  {
    int h = 1;
    while (h <= array.length / 3)
    {
      h = 3 *h + 1;	//h<=length/3
    }

    while (h > 0)
    {
      // similar to insertion
      for (int i = 0; i < array.length; i++)
      {
        int temp = array[i];
        int j;

        for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h)
        {
          array[j] = array[j - h];
        }

        array[j] = temp;
      }

      h = (h - 1) / 3;
    }

    return array;
  }
}

The output of shell Sort Algorithm in java:

---