## 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 SortBubble Sort

Optimized Bubble Sort

Insertion Sort

## 2. Algorithm

Below is a step by step algorithm for shell sort.

- The Shel Sort is an improved version of
**straight Insertion Sort**in which diminishing partitions are used to sort the data - 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.
- 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.

**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.

[packagecom.java.w3schools.blog.sorting;

importjava.util.Arrays;

/**

* Shell Sort program in Java

* *@authorVenkatesh *

*/

publicclassShellSortExample {

publicstaticvoidmain(String[] args) {

int[] array = { 50, 2, 5, 1, 49 };

System..println("Input Array = " + Arrays.outtoString(array));

shellsort(array);

System..println("After shell sort = " + Arrays.outtoString(array));

}

/* function to sort arr using shellSort */

staticintshellsort(intarr[]) {

intn = arr.length;

// Start with a big gap, then reduce the gap

for(intgap = 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(inti = 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

inttemp = arr[i];

// shift earlier gap-sorted elements up until the correct location for a[i] is

// found

intj;

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..println("After current gap(" + gap + ") : " + Arrays.outtoString(arr));

}

return0; }

}]

**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.

## No comments:

## Post a Comment

Please do not add any spam links in the comments section.