정렬7) 쉘 정렬(Shell Sort)

* 쉘 정렬
- 삽입정렬에서 최악의 경우 오래걸리는 문제접을 보완하기 위해 만들어진 정렬
- 기본 원리는 삽입정렬과 같으니, 비교 횟수가 더 적다


* 쉘 정렬 로직
    0. 원본 배열
    

    1. 원본 배열을 반으로 나눈 것으로 생각
    

    2. 일정 인덱스 만큼 뛰어 넘고 비교 정렬(같은 색)
    
        - 정렬된 후 배열 상태
        

    3. 반으로 나눠 정렬한 배열을 4로 나눈 것으로 생각
    

    4. 같은 색 끼리 삽입정렬 로직으로 정렬
    
        - 정렬된 후 배열 상태
        

    5. 위 과정과 같이 더 나누고 정렬


* 시간 복잡도
    - 나누는 간격 값에 큰 영향 받음
    - 최악의 경우: O(n^2)
    - 최선의 경우: O(n)
    - 일반적인 경우: