셸 정렬

셸 정렬(증분감소 정렬) 이 정렬 알고리즘은 삽입 정렬을 일반화한 것이다.
삽입 정렬은 입력 목록이 이미 어느 정도 정렬되어 있을 때 유용하다. 삽입 정렬에서 비교는 앞쪽의 정렬된 모든 요소에 대해 일어나며 한번에 정렬되지 않은 목록에서 선택된 하나의 요소만이 자신의 위치를 찾아간다. 이때 대부분의 비효율은 값의 교환 횟수가 많다는 것이다. 셸 정렬에서는 정렬해야할 배열을 여러 개의 부분 배열로 나누어 나뉘어진 배열에 대해 삽입 정렬로 사전 정렬을 수행한 후 전체 삽입 정렬을 수행하는 방식으로 동작한다. 이것은 서로 멀리 떨어진 요소간의 비교와 값의 교환을 용이하게 함으로써 삽입 정렬의 성느을 개선한다. 이 알고리즘은 다른 비교 알고리즘 중 2차원 복잡도 보다 작은 복잡도를 가진 최초의 알고리즘이다.

셸 정렬을 주어진 배열을 일정 크기의 부분 배열로 나눈 후 이 부분 배열들을 삽입 정렬한다. 다시 부분 배열들을 일정 크기로 다시 나누고 정렬하는 과정을 부분 배열의 크기가 1이 될때 까지 반복한다.
이때 부분 배열의 크기가 계속 일정 크기로 줄어드는 데 이 일련의 크기 값을 증분 시퀀스라고 한다. 이때 이 증분 시퀀스 값들을 만들 때 일정 규칙으로 정하는 것이 복잡도에 있어 최선의 결과를 준다고 한다. 셸 정렬은 이 부분 정렬을 수행하기 때문에 삽입 정렬에서 값을 삽입할때 삽입 위치 뒤쪽의 나머지 목록값들을 밀어내야 하는 밀어내기 횟수를 줄여 삽입 정렬의 효율성을 향상시키게 된다.

import java.util.Arrays;

public class ShellSort {

    public static void shellSort(int[] arr){
        int count=0;

        System.out.println("Before SelectionSort");
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
        System.out.println();

        int h = 1;

        while(h < arr.length) {
            h = 3*h + 1;
        }
        while(h>0){
            for(int i=h; i<arr.length; i++){
                count++;
                int temp = arr[i];
                int aux = i-h;
                while( ( aux>=0) && arr[aux] >temp){
                    arr[aux+h] = arr[aux];
                    aux = aux-h;
                }
                arr[aux+h] = temp;
            }
            h = h / 3;
        }


        System.out.println("After SelectionSort");
        System.out.println("The number of count : " + count);
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
        System.out.println();

    }
}

Before SelectionSort
77 2 53 77 85 30 80 100 46 51 
After SelectionSort
The number of count : 15
2 30 46 51 53 77 77 80 85 100