쉘 정렬

개요

삽입 정렬을 보완한 형태의 정렬.
삽입 정렬은 때에 따라 오른쪽 끝에 있는 요소를 왼쪽 끝으로 옮기기 위해 불필요한 Swap을 수행해야 할 수도 있다. 이를 막기 위해 Swap을 1 칸 단위로 수행하는 것이 아닌 그 이상의 값으로 수행하는 정렬.

---

복잡도

	최악	평균	최소
Big O 표기법	O(n^2)	O(n^1.5)	O(n)

 

---

알고리즘 절차

1. gap을 설정할 때, 전체 길이의 반절부터 시작해서 다음 단계에서는 그 길이의 반절, 그 다음에서는 또 그 길이의 반절로 설정을 하면 된다. 단, 해당 길이가 짝수일 경우, +1을 해 홀수로 만들어 준다.
2. 해당 gap이 결정되면 모든 범위를 커버할 수 있도록 인덱스 0부터 gap-1까지 반복합니다. 
   시작점과 gap을 가지고 insertSort를 수행하면 됨.

---

자바 코드

class Shell {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        shellSort(testCase1, testCase1.length);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    public static void insertSort(int[] arr, int low, int gap) {
        for(int i=low+gap; i<arr.length; i+=gap) {
            int tmp = arr[i];
            
            int j;
            for(j=i-gap; j>=low && arr[j] > tmp; j-=gap) {
                arr[j+gap] = arr[j];
            }   arr[j+gap] = tmp;
        }
    }
    
    public static void shellSort(int[] arr, int len) {
        for(int gap=len/2; gap>0; gap/=2) {
            if(gap % 2 ==0) {
                gap++;
            }
            
            for(int i=0; i<gap; i++) {
                insertSort(arr, i, gap);
            }
        }
    }
}