쉘 정렬(Shell Sort)

쉘 정렬

삽입 정렬을 보완한 알고리즘
1. 먼저 정렬해야할 리스트를 일정한 기준에 따라 분류
2. 연속적이지 않은 여러 개의 부분 리스트를 생성
3. 각부분 리스트를 삽입 정렬을 이용하여 정렬
4. 모든 부분 리스트가 정렬되면서 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘 반복
5. 부분 리스트의 개수가 1이 될때까지 반복

시간복잡도

최악 : O(n^2)
평균 : O(n^1.5)
최선 : O(n)

공간복잡도

O(n)

장점

삽입 정렬보다 뛰어나다

단점

간격(Gap) 잘못 설정시 성능이 굉창히 안좋아 진다

public class ShellSort {
 
    public static void main(String[] args) {
 
        int[] arr = {9, 4, 1, 7, 3, 2, 1, 5, 0, 6, 8};
        int len = arr.length;
 
        int temp = 0;
        int gap = len;
        for (; gap > 1;) {
            gap = (gap / 3) + 1;
            System.out.println("gap : " + gap);
            for (int i = 0; i < gap; i++) {// gap 만큼 반복한다
                //삽입 정렬 로직
                for (int j = i + gap; j < len; j += gap) {
                    /*
                    i : 묶음을 구분하기 위한 값
                    j : 삽입 정렬 종료 인덱스 
                     */
 
                    for (int x = i; x < j; x += gap) {
                        /*
                        x인덱스 ~ j인덱스 까지 반복하여 삽입정렬을 실행한다.
                         */
                        if (arr[x] > arr[j]) {
                            temp = arr[x];
                            arr[x] = arr[j];
                            arr[j] = temp;
                        }
                    }
                }
            }
 
            System.out.println(Arrays.toString(arr));
        }
 
    }
}