셸 정렬(Shell Sort)

🟩 삽입 정렬의 장점은 살리고, 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 

삽입 정렬의 보완

삽입 정렬은 초기 리스트가 "거의 보완"되어 있을 경우 효율적

 

정렬되지 않은상태의 배열에 대해 단순하게 삽입정렬을 적용하는 것이 아니라

'4-정렬', '2-정렬'처럼 조금이라도 정렬이 된 상태에 가까운 배열로 만든 다음 마지막 삽입정렬을 하는 것

정렬해야 하는 횟수는 늘지만, 전체적으로 요소 이동 횟수가 줄어들어 효율적인 정렬을 할 수 있다.

 

🟩 순서

1. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬 수행

2. 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다

3. 위의 과정을 그룹의 개수가 1이 될 때까지 반복한다.

 

🟩 나누는 간격 k

간격 k의 초깃값 : (데이터의 갯수) / 2

매 회전마다 k는 절반으로 나눈다. 항상 홀수가 되도록 값을 수정한다(짝수인 경우 + 1)

k가 1이 될 때까지 반복

'k-정렬'이라 부름 예) 5-정렬

 

 

🟩 장단점

(장) 연속적이지 않은 리스트의 교환이 일어나면 더 큰 거리를 이동

(장) 교환되는 요소들이 삽입정렬보다 최종위치에 있을 가능성이 더 높아진다.

(단) k 간격을 잘못 설정한다면 성능이 굉장히 안 좋아질 수 있다.

👉 보통 전체에서 h/2를 하지만 이보다 h/3 + 1이 더 빠르다.

 

🟩 시간복잡도

O(n^1.5)

ShellSort(A[ ], n)	{
	int i, j, temp;
    int gap = len / 2;
    while (gap > 0) {
        for (i = gap; i < len; i++) {
            temp = arr[i];
            j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}