Java Program To Shell Sort - Step by Step

1. Introduction

In this tutorial, We will learn how to implement the Shell Sort program in java.

First, We'll understand Shell Sort Algorithm then next see the java program on Shell Sort.

Shell sort is an algorithm that first sorts the elements far apart from each other and successively reduces the interval between the elements to be sorted. It is a generalized version of the insertion sort. In shell sort, elements at a specific interval are sorted.

Shell sort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting elements far apart from each other and progressively reducing the gap between them.

Read more on 

Selection Sort
Bubble Sort
Optimized Bubble Sort
Insertion Sort

2. Algorithm

Below is a step by step algorithm for shell sort.

1. The Shel Sort is an improved version of straight Insertion Sort in which diminishing partitions are used to sort the data
2. Next, Compare the elements that are distant apart rather than adjacents. That means not to compare the elements next to the element rather than this comparing the elements after a few elements like after 3 elements. You will understand in example illustration.
3. Finally, We start by comparing elements that are at a certain distance apart. So, If there are n elements then we start with a value gap < n.

There is a formulae to calculate value gap and gap value is considered as compare value after a certain elements.

[gap = floor(n/2));]

In the next iteration, the gap will be as follows. This continues until the gap reaches to 1 for every iteration.

[gap = floor(gap/2)]

4) In each pass, we keep reducing the value of the gap till we reach the last pass when gap is 1. 5) In the last pass, Shell sort is like an Insertion Sort.

2.1 Shell Sort Example 1

We will be seeing now for a smaller input.

[Input Array = [50, 2, 5, 1, 49]

Array Length = 5

Gap value = 5/2 = 2
After current gap : [5, 1, 49, 2, 50]

Gap value = 2/2 = 1
After current gap : [1, 2, 5, 49, 50]

After shell sort = [1, 2, 5, 49, 50]]

2.2 Shell Sort Example 2

For bigger input array.

[Input Array = [90, 2, 5, 6, 12, 99, 45, 20, 0, 100, 8]
Array Length = 11
Gap value = 11/2 = 5
After current gap : [8, 2, 5, 0, 12, 90, 45, 20, 6, 100, 99]
Gap value = 5/2 = 2
After current gap : [5, 0, 6, 2, 8, 20, 12, 90, 45, 100, 99]
Gap value = 2/2 = 1
After current gap : [0, 2, 5, 6, 8, 12, 20, 45, 90, 99, 100]
After shell sort = [0, 2, 5, 6, 8, 12, 20, 45, 90, 99, 100]]

3. Java Shell Sort Program Implementation

Below is the shell sort program in java. This program is compiled and run successfully.

[package com.java.w3schools.blog.sorting;

import java.util.Arrays;

/**
 * Shell Sort program in Java
 *  * @author Venkatesh *
 */
public class ShellSortExample {

public static void main(String[] args) {

int[] array = { 50, 2, 5, 1, 49 };
System.out.println("Input Array = " + Arrays.toString(array));
shellsort(array);
System.out.println("After shell sort =  " + Arrays.toString(array));

}
/* function to sort arr using shellSort */
static int shellsort(int arr[]) {
int n = arr.length;

// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {

// Do a gapped insertion sort for this gap size. he first gap elements
// a[0..gap-1] are already in gapped order keep adding one more element until
// the entire array is gap sorted

for (int i = gap; i < n; i += 1) {
// add a[i] to the elements that have been gap sorted save a[i] in temp and make
// a hole at position i

int temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for a[i] is
// found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}


// put temp (the original a[i]) in its correct location
arr[j] = temp;
}
System.out.println("After current gap(" + gap + ") :  " + Arrays.toString(arr));
}
return 0; }
}]

Output:

[Input Array = [50, 2, 5, 1, 49]
Array Length = 5
After current gap(2) : [5, 1, 49, 2, 50]
After current gap(1) : [1, 2, 5, 49, 50]
After shell sort = [1, 2, 5, 49, 50]]

4. Gap value in Shell Sort

To improve the performance, We must optimize the gap value.

The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yield a correct sort (as this makes the final pass an ordinary insertion sort); however, the properties of thus obtained versions of Shellsort may be very different. Too few gaps slow down the passes, and too many gaps produce an overhead.

Gap Sequence Reference

5. Conclusion

In this article, We have seen how to sort an array using shell sort. Gap value plays a vital role in time complexity and improves performance.

Seen the algorithm and java program for Shell Sort.

Time complexity is O(n2).

The code shown in this article is available over GitHub.

Shell Sort in Java