[JAVA] 쉘정렬(ShellSort)

쉘정렬: , (불안정) 간격을 두어 나눈 하위배열을 삽입정렬 반복

	package kr.opid.sorting;
	public class ShellSort {
	public static void main(String[] args) {
	int[] array = new int[10];
	array[0] = 33;
	array[1] = 11;
	array[2] = 99;
	array[3] = 1;
	array[4] = 22;
	array[5] = 88;
	array[6] = 55;
	array[7] = 44;
	array[8] = 66;
	array[9] = 77;
	System.out.println("before)");
	displayArray(array);
	System.out.println();
	System.out.println("after)");
	shellSort(array);
	}
	static int[] shellSort(int[] arr) {
	int gap = 1;
	while (gap <= arr.length / 3) {
	gap = gap * 3 + 1; // 크누스 간격순서
	}
	while (gap > 0) {
	for (int i = gap; i < arr.length; i++) {
	int tmp = arr[i];
	int idx = i;
	while (idx > gap - 1 && arr[idx - gap] >= tmp) {
	arr[idx] = arr[idx - gap];
	idx -= gap;
	}
	arr[idx] = tmp;
	}
	gap = (gap - 1) / 3;
	}
	return arr;
	}
	/**
	* 배열 출럭
	*
	* @param arr
	*/
	static void displayArray(int[] arr) {
	for (int i = 0; i < arr.length; i++) {
	System.out.print(arr[i] + " ");
	}
	}
	}

view raw ShellSort.java hosted with ❤ by GitHub