h(k)를 큰 수로 놓아서 순서가 맞지 않는 키들을 장거리 이동시킴으로써 일반 삽입정렬보다 빨리 제자리에 접근시키도록 하는 정렬
입력 배열을 부분배열로 나누너 정렬하는 과정을 여러번 걷침
부분배열의 크기와 개수를 변화시켜 가면서 과정을 진행
부분배열의 개수를 정하기 위해 양수로 이루어진 임의의 순열 h(k), h(k-1), ....h1 을 선택
이 순열에서 1<i<k 인 i 에 대하여 h(i-1) < h(i) < h(i=1) 이 항상 만족되도록 함
또한 임의의 i와 j에 대하여 i<j 이면 h(j)가 h(i)의 배수가 되지 않도록 한다
항상 h1=1이 되도록 한다.
첫째 단계에서 전체배열을 h(k) 개의 부분배열로 나누어 각 부분배열에 삽입 정렬을 적용
두 번째 단게에서 전체배열을 h(k-1) 개의 부분배열로 나누어 각 부분배열에 삽입 정렬 적용
이 과정을 계속하다가 마지막 단계에서는 h1개의 부분배열에서 삽입정렬을 적용시켜 정렬을 끝냄
쉡 정렬 예제
void ShellSort(vector<int> &array)
{
int h, i, j, value;
int n = array.size();
h = 1;
//부분배열 개수 결정
do h = 3 * h + 1; while (h < n);
do {
h /= 3;
//삽입정렬
for (i = h; i < n; i++)
{
value = array[i];
j = i;
while (array[j - h] > value) {
array[j] = array[j - h];
j -= h;
if (j <= h - 1) break;
}
array[j] = value;
}
} while (h > 1);
}
