ShellSort.java

package test;

import java.util.Arrays;

public class ShellSort {
	private final static int[] gap = 
		{ 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 	
		8858, 19930, 44842, 100894, 227011, 510774,
		1149241, 2585792, 5818032, 13090572, 29453787, 
		66271020, 149109795, 335497038, 754868335, 1698453753 };	// 갭을 담고있는 배열
	
	public static void main(String[] args) {
//		int[] arr = {6, 3, 2, 7, 1, 5, 0, 9, 8, 4};
		int[] arr = new int[25];
		for(int i = 0 ; i < arr.length ; i++) {
			arr[i] = (int)(Math.random() * 101);
		}
		
		System.out.println(Arrays.toString(arr));
		System.out.println();
		
		int index = getGap(arr.length);
		System.out.println();
		
		for(int i = index ; i >= 0 ; i--) {
			System.out.println("gap : " + gap[i]);
			for(int j = 0 ; j < gap[i] ; j++) {
				insertionSort(arr, j, arr.length, gap[i]);
			}
			System.out.println();
			System.out.println("------------------------------------------------------------------------------------------------------------------------------------------------------");
		}
		
		System.out.println();
		System.out.println(Arrays.toString(arr));
	}
	
	private static int getGap(int length) {
		int index = 0;
		
		int len = (int)(length / 2.25);
		while(gap[index] < len) {
			System.out.println(index + " : " + gap[index] + " < " + len);
			index++;
		}
		return index;
	}
	
	private static void insertionSort(int[] arr, int start, int size, int gap) {
		for(int i = start + gap ; i < size ; i += gap) {
			int target = arr[i];
			int j = i - gap;
			
			while(j >= start && target < arr[j]) {
				System.out.println(i + " ▶ " + j + "(" + arr[j] + ")" + " ← " + (j + gap) + "(" + target + ")" + " : " + Arrays.toString(arr));
				arr[j + gap] = arr[j];
				j -= gap;
			}
			arr[j + gap] = target;
		}
	}
}