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, 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.
1) The Shel Sort is an improved version of straight Insertion Sort in which diminishing partitions are used to sort the data.
2) 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) 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.
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.
We will be seeing now for a smaller input.
3. Java Program Implementation
Below is the shell sort program in java. This program is compiled and run successfully.
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
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.
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 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 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 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;
}
}
Ouput:
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
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.
0 Comments