Thursday, May 5, 2022

Question 83 : Implement shell sort in java?

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell.

It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. 

Last step of shell sort is ultimately insertion sort.
In short, it improves insertion sort by comparison and exchange elements that are far away.

Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over array and sort number of equally sized array using insertion sort

Java program to implement shell sort:

import java.util.Arrays; public class ShellSortMain { public static void main(String[] args) { int[] array = { 22, 53, 33, 12, 75, 65, 887, 125, 37, 977 }; System.out.println("Before Sorting : "); System.out.println(Arrays.toString(array)); System.out.println("==================="); System.out.println("After Sorting : "); array = shellsort(array); System.out.println(Arrays.toString(array)); } private static int[] shellsort(int[] array) { // first part uses the Knuth's interval sequence int h = 1; while (h <= array.length / 3) { h = 3 * h + 1; // h is equal to highest sequence of h<=length/3 // (1,4,13,40...) } // next part while (h > 0) { // for array of length 10, h=4 // This step is similar to insertion sort below 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; } }

When you run above program, you will get below output:
Before Sorting : [22, 53, 33, 12, 75, 65, 887, 125, 37, 977] =================== After Sorting : [12, 22, 33, 37, 53, 65, 75, 125, 887, 977]

Time complexity:
Best case: O(n)
Average case: Depends on gaps
Worst case : o(nlog2n)

Don't miss the next article! 

Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS