import java.util.Scanner;

public class coba {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("SHELL SORTING");
        System.out.print("Enter the number of elements : ");
        int n = sc.nextInt();
        int arr[] = new int[n];
        System.out.println("Enter " + n + " elements :");
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        System.out.print("Before sorted array : ");
        for(int x = 0; x < n; x++)
            System.out.print(arr[x]+" ");
        shellSort(arr);

        System.out.print("\nAfter sorted array : ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    static void shellSort(int[] nums) {
        int h = 1;
        int n = nums.length;
        while(h < n) {
                h = h * 3 + 1;
        }
        h = h / 3;
        int c, j;
        
        while (h > 0) {
            for (int i = h; i < n; i++) {
                c = nums[i];
                j = i;
                while (j >= h && nums[j - h] > c) {
                    nums[j] = nums[j - h];
                    j = j - h;
                }
                nums[j] = c;
            }
            h = h / 2;
        }
    }
}