In this tutorial, we will learn how to implement Shell Sort in java. First, we will start by understanding the Shell Sort algorithm.
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:
Implementation of Shell sort in java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | 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:
