public class ShellSort {

	/* An utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    /* function to sort arr using shellSort */
    int sort(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.
            // The 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;
            }
        }
        return 0;
    }

    // Driver method
    public static void main(String args[])
    {
        int arr[] = {12, 34, 54, 2, 3};
        System.out.println("Array before sorting");
        printArray(arr);

        ShellSort ob = new ShellSort();
        ob.sort(arr);

        System.out.println("Array after sorting");
        printArray(arr);
    }
}
/*
 * public class ShellSort {
    /* An utility function to print array of size n*/

    /* function to sort array using shellSort */
   // void sort(int A[])
   // {
      //  int n = A.length;

        // Start with a larger gap, then reduce the gap to 1
        // we take gap sequence in order of |N/2|, |N/4|, |N/8|...1
      //  for (int gap = n/2; gap > 0; gap /= 2)
       // {
            // we perform gapped insertion sort for this gap size.
            // The 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) {
                // store a[i] in temp and make a hole at
                // position i
               // int temp = A[i];
                // shift earlier gap-sorted elements up until
                // the correct location for a[i] is found
                //int j;
                //for (j = i; j >= gap && A[j - gap] > temp; j -= gap)
                  //  A[j] = A[j - gap];
  //
                // put temp (the original a[i]) in its correct
                // location
              //  A[j] = temp;
            //}
       // }
    //}

    // Driver method
   // public static void main(String args[])
   // {
    //    int arr[] = {61,109,149,111,34,2,24,119,122,125,27,145};
      //print unsorted array using Arrays.toString()
      //  System.out.print("Unsorted array: ");
       // System.out.println(Arrays.toString(arr));

       // ShellSort ob = new ShellSort();
       // ob.sort(arr);

       // System.out.print("Sorted array: ");
        //print sorted array
       //   System.out.println(Arrays.toString(arr));
   // }