쉘 정렬 (Shell Sort)

1. 쉘 정렬

간격(gap)을 이용해서 굵직굵직한 삽입정렬을 하자

 

※ 삽입정렬은 어느 정도 이미 정렬된 배열에서 효과적

    ∴   1. 간격을 이용해서 굵직굵직한 그룹별 삽입 정렬을 한다. (큰 숫자들 대충 뒤로, 작은 숫자들 대충 앞으로)

          2. 큰 틀에서 어느정도 정렬이 된 상태가 된다.

          3. 이후에 정석 삽입정렬을 해서 완벽히 정렬

 

 

※ gap

     전체 원소 수의 1/2  →  이전 gap의 1/2  →  이전 gap의 1/2  → ...... →  1

 

 

 

2. 쉘 정렬 예제

ex )  30 60 90 10 40 80 40 20 10 60 50 30 40 90 80  오름차순 정리하시오.

 

#include <stdio.h>

void shellSort(int arr[], int len) {
    
    for(int h=len/2 ; h>0 ; h/=2) {
        
        for(int i=0 ; i<h ; i++) {
            
            for(int j=h+i ; j<len ; j+=h) {   // i번째 그룹 삽입정렬 현재 주자 temp = arr[j] 
            // temp는 i번째 그룹의 index = 1인 2nd 원소 (원래 삽입 정렬은 index = 1 부터가 첫번째 주자)
                int temp = arr[j];
                int idx = j;            
                
                
                // 하극상인 애 나올때까지 현재 주자 바로 앞 부분을 h간격으로 하나씩 살펴보기
                // 하극상 발견되면 현재 주자랑 하극상 자리 바꾸기 (삽입)
                // 바꾸고 나서도 바로 앞 부분을 h간격으로 살펴보며 또 하극상인 애 있는지 확인 후 반복
                while(arr[idx-h] > temp && idx >= h) {   
                    arr[idx] = arr[idx-h];    
                    idx -= h;
                }
                
                arr[idx] = temp;
            }
        }
    }
    
    for(int i=0 ; i<len ; i++) {
        printf("%d ", arr[i]);
    }
}


int main() {
    int arr[] = {30, 60, 90, 10, 40, 80, 40, 20, 10, 60, 50, 30, 40, 90, 80};
    int len = sizeof(arr) / sizeof(int);
    
    shellSort(arr, len);
    
    return 0;
}