[알고리즘] 쉘 정렬 (Shell Sort)

쉘정렬이란, 선택정렬의 인접한 레코드를 바꿔 그룹을 나누어, 그룹마다의 선택정렬을 수행하는 정렬 방식을 통해 느려짐을 완화한 정렬 방식이다.  ( 쉘 정렬의 경우 그룹의 크기만큼 레코드 이동이 가능해짐! )

void ShellSort(int A[], int n){
    //입력 : A[0:n-1],n: 정렬할 원소의 개수
    //출력 : A[0:n-1] : 정렬된 배열
    int h,i,j,Value;
    h=1;
    do h = 3*h+1; while (h < n);
    //n을 넘지 않는 h값을 찾아서 진행
    //n이 15라면, h=13 -> h->4 -> h=1로 진행된다.
    do {
        h=h/3;
        for (i=h; i<n; i++){
            Value = A[i];
            j=i;
            while(A[j-h]>Value){
                A[j]=A[j-h];
                j -= h;
                if (j<h) break;
            } A[j] = Value;
        }
        while (h>1);

쉘의 크기를 정하는 일반적 공식

n을 넘지 않는 h값을 찾아서 진행한다.

선택정렬과의 차이점 : 이전값과 바꾸는 것이 아닌 이전 그룹의 같은 순서의 값과 비교하며 조건에 부합한다면 자리를 바꾸기 때문에 훨씬 빠르다.

 

• 제자리성 : 제자리 정렬 (상수크기 메모리)
• 안정성 : 분안정한 정렬 (인접한 레코드와 자리바꾸는 것이 아니기 때문)
• 최악시간복잡도 :  n의3/2제곱 (실제 정렬의 성능은 h값 설정에 따라 달라진다.)