셸 정렬(Shell Sort)
0. 셸 정렬(Shell Sort)이란?
'Donald L. Shell'이라는 사람이 제안한 방법, 삽입 정렬을 보완한 방법.
정렬할 배열의 요소를 그룹으로 나누어 그룹 별로 삽입 정렬을 수행하고 두 그룹을 합치면서 정렬을 반복하여 이동 횟수를 줄이는 방법.
1. 셸 정렬(Shell Sort) 알고리즘 예제
[5, 3, 8, 1, 2, 7]의 배열
- 1회차
순차적으로 확인하여 작은 값인 3을 앞 부분으로 삽입
...
- 최종
1 2 3 5 7 8로 정렬을 완성
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)2. 셸 정렬(shell sort)의 특징
- 장점
- 연속적이지 않은 부분에서 자료의 교환이 일어나면 더 긴 이동을 한다. 따라서 교환되는 요소들이 삽입 정렬보다 최종 위치에 있을 가능성이 높아진다.
- 삽입 정렬보다 빠른 속도로 수행된다.
- 알고리즘이 간단하여 구현이 쉽다.
3. 셸 정렬(shell sort)의 시간복잡도
- 평균: T(n) = O(n^(1.5))
- 최악의 경우: T(n) = O(n²)
