Shell Sort The following example shows shell sort implementation.
Best case time complexity of shell sort is O(n)
Worst case time complexity of shell sort is O(n log2 n)
Average case time complexity of shell sort is O(n log2 n)
package com.bethecoder.tutorials.ds.sort; import java.util.Arrays; public class ShellSort { /** * @param args */ public static void main ( String [] args ) { int [] list = { 112 , 23 , 376 , 6 , 5 , 1 , 8 , 3 , 9 , 4 , 0 , 2 , 7 , 11 , 26 , 12 , 19 , 27 , 86 , 19 } ; System.out.println ( "Before sort : " + Arrays.toString ( list )) ; double timeTaken = shellSortTimeTaken ( list ) ; System.out.println ( "After sort : " + Arrays.toString ( list )) ; System.out.println ( "Time taken for ShellSort : " + timeTaken + " milliseconds." ) ; } public static void shellSort ( int [] list ) { int h = 1 ; while (( h* 3 + 1 ) < list.length ) { h = h* 3 + 1 ; } while ( h > 0 ) { for ( int colIndex = h- 1 ; colIndex < list.length; colIndex++ ) { int val = list [ colIndex ] ; int j = colIndex; //Sort column wise while ( j>=h && list [ j-h ] > val ) { list [ j ] = list [ j-h ] ; j = j-h; } list [ j ] = val; } h = h/ 3 ; } } /** * Sorts and returns the time taken in milliseconds. * * @param list * @return */ public static double shellSortTimeTaken ( int [] list ) { long startTime = System.nanoTime () ; shellSort ( list ) ; long timeTaken = System.nanoTime () - startTime; return timeTaken * Math.pow ( 10 , - 6 ) ; } }
Before sort : [112, 23, 376, 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19, 19, 23, 26, 27, 86, 112, 376]
Time taken for ShellSort : 0.007821999999999999 milliseconds.
