쉘정렬(shell sort)

쉘정렬(shell sort)

---

정렬하는 간격을 줄여나가는 삽입정렬 형식

원리

1. 전체 리스트를 간격 별로 나눔 (간격 : 초깃값(배열의 절반) → 이전 간격의1 / 2 → 간격 1)
2. 각 간격에대해 삽입정렬 수행

pseudocode

쉘정렬(base : 배열시작주소, n : 배열요소 개수)
    반복(gap : n/2 -> 1) // gap을 점차 줄이면서 반복
        반복(i : gap -> n) // gap 간격에 맞춰 위치 선택
            key = base[i]
            반복(j : i-gap -> 0 && base[j] > key) // gap 간격으로 정렬
                base[j+gap] = base[j] // gap 간격으로 앞부분을 한 칸씩 뒤로 이동
            base[j+gap] = key

best case 시간복잡도 : $O(n)$
avg case 시간복잡도 : $O(n^{3/2})$
worst case 시간복잡도 : $O(n^2)$
안정성 : 불안정
장점 : 정렬이 어느 정도 정렬시 매우 효율적
단점 : 많은 이동(1칸씩 밀기) → record가 클수록 불리

실제코드

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int i,j;
    int arr[20] = {
        3,5,2,2,4,
        6,1,3,7,8,
        2,11,2,21,20,
        12,14,1,6,16};
    int n = sizeof(arr)/sizeof(int);
    int count = 0;
    //gap을 절반으로 줄여나가는 반복문
    for(int gap = n/2 ; gap > 0 ; gap /= 2){
        //gap에서 시작하여 배열의 끝까지 반복
        for(int i = gap ; i < n ; i++){
            int temp = arr[i];
            int j;
            //삽입 정렬을 수행하는 부분
            for(j = i ; (j >= gap) && (arr[j-gap] > temp) ; j -= gap ){
                arr[j] = arr[j-gap];
            }
            arr[j] = temp;
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    
    return 0;
}