$show=/label

Java Program To Shell Sort - Step by Step

SHARE:

A quick guide to Java Program to Shell Sort and along with the algorithm. And also a java example to implement Shell Sort which is in-place comparison sort..

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.

Java Program To Shell Sort - Step by Step


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

COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,31,ArrayList,16,Arrays,2,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,4,Collections,20,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,5,Core Java,72,Corona India,1,Create,2,CSS,1,Date,2,Date Time API,3,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,2,Fast,1,Files,9,Float,1,Font,1,For examples,1,For loop examples,1,For Loop in Java,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Inner for loops,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,28,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,java 5 For loop,1,Java 8,48,Java 9,1,Java Design Patterns,1,Java Files,1,Java for loop,1,Java Program,2,Java Programs,65,java.lang,5,java.util. function,1,jQuery,1,Kotlin,10,Kotlin Programs,6,Lambda,1,lang,29,Leap Year,1,live updates,1,Mac OS,2,Math,1,Maven,1,Method References,1,Mockito,1,MongoDB,3,Nested for loop,1,Nested for loop examples,1,New Features,1,Operations,1,Optional,4,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Stream,3,Streams,11,String,48,String Programs,8,String Revese,1,Swing,1,System,1,Tags,1,Threads,8,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,2,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program To Shell Sort - Step by Step
Java Program To Shell Sort - Step by Step
A quick guide to Java Program to Shell Sort and along with the algorithm. And also a java example to implement Shell Sort which is in-place comparison sort..
https://1.bp.blogspot.com/-gJjOT_Wi9Vo/XSmllw5WZmI/AAAAAAAABuQ/ghqXx4XmXIstMCsWvRG5Evxn9DsaRBDXQCLcBGAs/s320/Shell%2BSort%2BProgram%2Bin%2BJava%2B.png
https://1.bp.blogspot.com/-gJjOT_Wi9Vo/XSmllw5WZmI/AAAAAAAABuQ/ghqXx4XmXIstMCsWvRG5Evxn9DsaRBDXQCLcBGAs/s72-c/Shell%2BSort%2BProgram%2Bin%2BJava%2B.png
JavaProgramTo.com
https://www.javaprogramto.com/2019/07/java-shell-sort.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2019/07/java-shell-sort.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content