셸 정렬

설명

셸 정렬은 gap(특정 간격)이 1이 될때까지 gap의 간격만큼 삽입 정렬이 이뤄진다.

• 셸 정렬은 삽입 정렬에서 인접한 원소끼리만 비교가 이뤄지는 단점을 gap을 기준으로 비교함으로써 보완했다.
• gap만큼 떨어진 원소들을 비교하며 삽입 정렬함으로써 비교해야하는 원소들의 간격이 떨어져 있을 경우, 기존의 삽입 정렬에서 효율성이 떨어지는 것을 보완한 것이다.
• gap이 1일 때에는 삽입 정렬과 동일하게 작동한다(하단의 그림 참조).

• gap을 키우면 아래와 같이 gap만큼 떨어진 원소들을 비교하며 삽입 정렬이 이뤄진다.
  
  

• 즉, 간격에 초점을 맞추기 보다는 삽입 정렬에 초점을 맞추되, 특정 간격만큼 떨어진 원소들끼리 비교한다고 생각하면 이해하는데 도움이 될 것이다.

구현

public static void shellSort(int[] arr) {
    int len = arr.length;
	
    // gap이 1이 될때까지 크기를 절반씩 줄임
    for(int gap = len / 2; gap > 0; gap /= 2) {
    	// gap만큼 떨어진 원소들 간에 삽입 정렬
        for(int i = gap; i < len; i++) {
            int j = i;
            int key = arr[j];
			
            for(j = i; j >= gap && key < arr[j - gap]; j -= gap) {
                arr[j] = arr[j - gap];
			}
        	arr[j] = key;
		}
	}
}

셸 정렬 구현 코드

시간복잡도

• gap을 어떻게 설정하느냐에 따라 다름
• n/2 또는 n/4 처럼 나누는 경우
  최선: O(N)
  평균: O(N^1.5)
  최악: O(N^2)
• 삽입 정렬의 단점을 보완한 방식임으로 평균적인 시간 복잡도는 조금 더 빠르나, 배열이 역순으로 되어 있을 경우 삽입 정렬과 마찬가지로 O(N^2)이라는 시간복잡도를 갖음