Shell sorting in java





Contents of page >
  • Full Program/SourceCode/Example of Shell sorting in java >
  • Complexity of Shell sorting in java >



Also read : Radix sort



Full Program/SourceCode/Example of Shell sorting in java >
/**
*  write a program to sort array using Shell Sort in java.
*/
public class ShellSort {
  
   /**
   * Declare initialize array which has to be sorted using Shell sort in java
   */
  
   private int[] arr = {12, 3, 8, 9, 1, 14, 6, 7, 5};
   /**
   * This method Sort Array using Shell Sort in java
   */
   public void shellSort() {
          int h = 1; // Keep initial value of h as 1
          int inner, outer, temp;
         
          while (h <= arr.length / 3){
                 h = h * 3 + 1; //As initial of h is 1, It will form series as (1, 4, 13, 40 and so on)
          }
         
          while (h > 0){ // Keep on decreasing h, until h>1
                 for (outer = h; outer < arr.length; outer++) {
                       temp = arr[outer];
                       inner = outer;
                      
                       while (inner > h - 1 && arr[inner - h] >= temp) {
                              arr[inner] = arr[inner - h];
                              inner = inner - h;
                       }
                       arr[inner] = temp;
                 } //End for
                 h = (h - 1) / 3;
          } //End while
         
   }
  
   /**
   * This method Display Array
   */
   public void display(){
          for (int i = 0; i < arr.length; i++){
                 System.out.print(arr[i] + " ");
          }
   }
   public static void main(String[] args) {
         
          ShellSort shellSort = new ShellSort();
          System.out.print("Display Array elements before Shell sorting : ");
          shellSort.display(); // display unsorted array
         
          shellSort.shellSort(); // shell sort the array
         
          System.out.print("\nDisplay Array elements after Shell sorting  : ");
          shellSort.display(); // display sorted array
         
   }
  
}
/*output
Display Array elements before Shell sorting : 12 3 8 9 1 14 6 7 5
Display Array elements after Shell sorting  : 1 3 5 6 7 8 9 12 14
*/

So, we wrote program to do shell sort of array in java.


Complexity of Shell sorting in java >
Best Case :    O(n log n), when array is already sorted.
Average Case :  O((n log n)2)
Worst Case :      The worst case too is O((n log n)2).

Summary >
So in this data structure tutorial we learned Program/Example of Shell sorting in java. Complexity of Shell sorting in java.

Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.



eEdit
Must read for you :