셸 정렬(Shell Sort)의 개념
앞서 알아봤던 삽입 정렬은 삽입될 곳이 현재 위치에서 많이 멀 경우에도 한 번에 한 자리씩만 이동하므로 제자리를 찾는 데 느리다는 단점을 가집니다. 셸 정렬은 멀리 떨어진 원소를 교환하여 처리 속도를 향상시킬 수 있도록 개선시킨, 도널드 셸이라는 사람이 고안해낸 알고리즘입니다.
셸 정렬의 아이디어는 정렬할 배열을 몇 개의 부분배열로 나눈 다음, 각 부분배열에 대해서 삽입 정렬을 수행한 다음 점차 간격을 줄여 삽입 정렬을 수행하여 “부분 배열일 때에는 한 칸 옆의 원소를 비교하고 이동하는 것이지만, 전체 배열의 관점에서 보면 멀리 떨어진 원소를 비교하고 이동하여 빠른 속도로 제자리를 찾도록 하는 것” 입니다.
셸 정렬의 Python 구현
Python 으로 셸 정렬을 아래와 같이 구현할 수 있습니다.
def shell_sort(arr: list) -> None:
n = len(arr)
gap = n // 2 # 초기 간격을 설정합니다.
# 간격의 크기를 줄여가며 반복합니다.
while gap > 0:
# 각 서브 리스트에 대해 삽입 정렬을 수행합니다.
for i in range(gap, n):
key = arr[i]
j = i
# 현재 요소를 간격만큼 뒤에 있는 요소들과 비교하며 적절한 위치에 삽입합니다.
while j >= gap and arr[j - gap] > key:
arr[j] = arr[j - gap]
j -= gap
arr[j] = key
gap = gap // 2
위의 코드는 아래와 같이 동작합니다.
먼저, 초기 간격을 설정합니다. 초기 간격은 간단히 배열의 크기 // 2 로 가정합니다. 하여, 아래와 같이 하나의 큰 배열은 네 개의 부분배열로 나누어지게 됩니다. (배열이 나누어지는 방식은 인덱스로 결정된다는 사실을 기억하세요. 아래처럼 “실제로” 배열이 [35, 14, 33 19 ...] 처럼 나누어지지 않습니다.)
# 0 1 2 3 4 5 6 7 (인덱스)
[35, 33, 42, 10, 14, 19, 27, 44]
# 나눠진 후 (인덱스 0,4 / 1,5 / 2,6 / 3,7)
gap1 | gap2 | gap3 | gap4
[35, 14] [33, 19] [42, 27] [10, 44]나눠진 부분배열에 대해서 모두 삽입 정렬을 수행합니다. 첫 번째 삽입 정렬이 끝나면, 아래와 같은 형태가 됩니다.
gap1 | gap2 | gap3 | gap4
[14, 35] [19, 33] [27, 42] [10, 44]
# 실제 배열의 상태
[14, 19, 27, 10, 35, 33, 42, 44]이제 간격을 2로 줄인 다음, 부분 배열을 만듭니다.
gap1 | gap2
[14, 27, 35, 42] [19, 10, 33, 44]그리고, 부분 배열에 대해서 또 삽입 정렬을 수행합니다.
gap1 | gap2
[14, 27, 35, 42], [10, 19, 33, 44]
# 실제 배열의 상태
[14, 10, 27, 19, 35, 33, 42, 44]이제, 간격을 1로 줄입니다. 간격을 1로 줄인다는 것은 전체 배열을 의미하고, 전체 배열에 대해서 삽입 정렬을 수행합니다.
gap1
[14, 10, 27, 19, 35, 33, 42, 44]
# 간격이 1인 상태에서(전체 배열에 대해서) 삽입 정렬 수행 후 배열의 상태
[10, 14, 19, 27, 33, 35, 42, 44]셸 정렬의 성능 분석과 특징
- 최악의 경우, 시간 복잡도는
O(n^2)입니다. - 최선의 경우, 시간 복잡도는
O(nlogn)입니다. - 예제에서는 간단하게 간격을
배열의크기 / 2로 정했지만, 간격의 크기를 계산하는 방식에 따라 성능이 달라집니다. - 같은 값을 가진 여러 개의 데이터에 대해서 정렬 전의 상대적인 순서가 유지되지 않는 안정적이지 않은 정렬 알고리즘입니다.
- 데이터가 저장된 공간 이외의 추가적인 저장공간으로 상수 개가 필요한 제자리 정렬 알고리즘입니다.