package basic.sort;

import java.util.Arrays;

import java.util.Random;

public class ShellSort {

    public static <AnyType extends Comparable<? super AnyType>>

    void shellSortOnce(AnyType a[]){

        AnyType temp;

        if((a==null)||(a.length==0)){

            return ;

        }

        for(int gap = a.length /2 ; gap > 0 ;gap = gap /2){

            for(int i = gap ; i<a.length; i++){

                AnyType tmp = a[i];

                int j = i;

                for( ; j >= gap && tmp.compareTo(a[j - gap]) < 0 ; j -= gap){

                    a[j] = a[j-gap];

                }

                a[j] = tmp ;

            }

        }

    }

    public static void main(String[] args){

        Random rand = new Random();

        Integer[] arr = new Integer[10];

        for(int i = 0 ;i <10 ;i++){

            arr[i] = rand.nextInt(1000);

        }

        println(Arrays.toString(arr));

        shellSortOnce(arr);

        println(Arrays.toString(arr));

    }

    public static void println(String str){

        System.out.println(str);

    }

}