tl  tr
  Home | Tutorials | Articles | Videos | Products | Search
Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 
 Data Structures > Sort > Shell Sort

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 log2n)
  • Average case time complexity of shell sort is O(n log2n)

File Name  :  
com/bethecoder/tutorials/ds/sort/ShellSort.java 
Author  :  Sudhakar KV
Email  :  kvenkatasudhakar@gmail.com
   
package com.bethecoder.tutorials.ds.sort;

import java.util.Arrays;

public class ShellSort {

  /**
   @param args
   */
  public static void main(String[] args) {

    int[] list = 11223376651839402711261219278619 };
    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);
  }
}
   

It gives the following output,
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.


                    Print

   


Books Recommendation

 
 
bl  br