[문법] 셸 정렬(shell sort) 개념 및 구현(Python)

셸 정렬이란?

삽입정렬을 보완한 알고리즘이다.
- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안
    - 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동
    - 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
    - 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.

• 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 ‘간격(gap)’ 이라고 한다.
  - 간격의 초깃값: (정렬할 값의 수)/2
  - 생성된 부분 리스트의 개수는 gap과 같다.
• 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
  - 간격은 홀수로 하는 것이 좋다.
  - 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
• 간격 k가 1이 될 때까지 반복한다.

 

특징

• 장점
  - 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.
  - 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.
  - 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다.

 

시간복잡도

• 평균: T(n) = O(n^1.5)
• 최악의 경우: T(n) = O(n^2)

 

구현 (Python)

def shell_sort(arr):
    N = len(arr)
    h = N // 2
    while h > 0:
        for i in range(h, N):
            temp = arr[i]
            j = i - h
            while j >= 0 and arr[j] > temp:
                arr[j + h] = arr[j]
                j -= h
            arr[j + h] = temp
        h //= 2
 
    print(arr)
 
 
arr = [8, 1, 4, 2, 7, 6, 3, 5]
shell_sort(arr)