셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다.
단순 삽입 정렬의 문제
다음 배열에 단순 삽입 정렬을 적용해보자
두 번째 원소부터 주목하여 2, 3, 4, 5를 순서대로 선택하며 정렬한다.
여기까지는 이미 정렬을 마친 상태이므로 원소의 이동(값의 대입)은 발생하지 않는다. 이 단계까지는 아주 빠르게 완료한다. 그러나 아래 그림과 같이 여섯 번째 원소인 0을 삽입 정렬하려면 총 6번에 걸쳐 원소를 이동(대입)해야 한다.
단순 삽입 정렬은 다음과 같은 특징이 있다.
- 장점: 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다.
- 단점: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.
셸 정렬 알아보기
단순 삽입 정렬의 장점을 살리면서 단점을 보완한 것이 도널드 L.셸이 고안한 셸 정렬 알고리즘이다.
셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법이다.
아래 그림에서의 배열을 예로 들어 알고리즘을 이해해보자.
먼저 서로 4칸씩 떨어진 원소를 꺼내어 (8, 7), (1, 6), (4, 3), (2, 5)의 4개 그룹으로 나누고 그룹별로 각각 정렬한다.
즉 ①은 (8, 7)을 정렬하여 (7, 8)로, ②는 (1, 6)을 정렬하여 (1, 6)으로, ③은 (4, 3)을 정렬하여 (3, 4)로, ④는 (2, 5)를 정렬하여 (2, 5)로 만든다.
이처럼 서로 4칸 떨어진 원소를 정렬하는 방법을 '4-정렬'이라고 한다. 아직 정렬을 마치진 않았지만 정렬을 거의 마친 상태에 가까워진다.
이어서 2칸 떨어진 원소를 모두 꺼내 (7, 3, 8, 4), (1, 2, 6, 5)의 두 그룹으로 나누고 '2-정렬'을 수행한다.
정렬을 마치고 나면 아래 그림과 같이 (3, 4, 7, 8)과 (1, 2, 5, 6)이 된다.
이렇게 해서 얻은 배열은 좀 더 정렬된 상태에 가까워진다. 마지막으로 '1-정렬'을 적용하여 1칸 떨어진 배열, 즉 배열 전체에 적용하면 정렬이 완료된다.
아래 그림을 통해 셸 정렬의 전체 흐름을 볼 수 있다.
셸 정렬 과정에서 수행하는 각각의 정렬을 h-정렬이라고 한다.
아래 그림은 h값을 4, 2, 1로 감소시키면서 정렬을 총 7번 수행하여 정렬을 완료한다.
- 2개 원소에서 4-정렬을 수행(4개 그룹, 4번)
- 4개 원소에서 2-정렬을 수행(2개 그룹, 2번)
- 8개 원소에서 1-정렬을 수행(1개 그룹, 1번)
→ 총 7번 정렬
a 배열을 바로 단순 삽입 정렬하지 않고 '4-정렬'과 '2-정렬'을 먼저 수행하여 정렬을 거의 마친 상태인 c를 만든다.
그리고 마지막으로 단순 삽입 정렬을 한 번 수행하여 정렬을 완료하는 것이다.
이렇듯 셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해 사용한다.
정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적이다.
아래는 셸 정렬을 수행하는 프로그램이다.
# 셸 정렬 알고리즘 구현하기
from typing import MutableSequence
def shell_sort(a: MutableSequence) -> None:
"""셸 정렬"""
n = len(a)
h = n // 2
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 2
if __name__ == '__main__':
print('셸 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
shell_sort(x) # 배열 x를 셸 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
셸 정렬을 수행합니다.
원소 수를 입력하세요.: 8
x[0]: 8
x[1]: 1
x[2]: 4
x[3]: 2
x[4]: 7
x[5]: 6
x[6]: 3
x[7]: 5
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8
Process finished with exit code 0
위 프로그램의 while 문 내부 코드는 단순 삽입 정렬을 수행하는 과정으로 단순 삽입 정렬의 코드와 거의 같다.
다른 점이 있다면 주목하는 원소와 비교하는 원소가 서로 이웃하지 않고 h개만큼 떨어져 있다는 것이다.
그리고 h의 초깃값은 n // 2로 구한다(전체 배열의 절반값이기 때문이다).
그리고 while문을 반복할 때마다 다시 2로 나눈 값으로 업데이트 한다. 즉, h는 다음과 같이 변화한다.
- 원소 수가 8이면 4 → 2 → 1
- 원소 수가 7이면 3 → 1
이제 h값을 선택하는 방법을 알아보자.
h값의 선택
앞에서 원소 수인 n값이 8이라면 h값을 다음과 같이 변화시킨다.
- h = 4 → 2 → 1
h값은 n부터 감소하다가 마지막에는 1이 된다. 그렇다면 h값을 어떤 수열로 감소시키면 효율적인 정렬을 할 수 있을지 알아보자.
아래 그림을 보면서 배열 그룹을 나누는 과정부터 다시 살펴보자.
a를 학생 8명의 점수라고 가정했을 때 그림 b처럼 학생 2명씩 4개 그룹으로 나누어 정렬할 수 있다.
그런 다음 c처럼 학생 4명씩 2개 그룹으로 나누어 다시 정렬한다. 여기서 b의 두 그룹을 합쳐서 c가 되는 과정을 잘 살펴보자.
그림에서 파란색 그룹 ((8, 7), (4, 3))과 검은색 그룹((1, 6), (2, 5))은 섞이지 않는다. 그런데 이렇게 두 그룹이 섞이지 않은 상태에서 c로 함치면 다시 처음 단계인 a와 같아진다.
이는 애써 그룹으로 나누어서 정렬했지만 충분히 그 기능을 하지 못한다는 것을 보여준다.
이 문제를 해결하려면 h값이 서로 배수가 되지 않도록 해야 한다. 그러면 원소가 충분히 뒤섞이므로 효율 좋은 정렬을 기대할 수 있다. 다음 수열을 사용하면 셸 정렬 알고리즘을 간단하게 만들 수 있고 효율적인 정렬도 할 수 있다.
- h = … → 121 → 40 → 13 → 4 → 1
이 수열을 거꾸로 살펴보면 1부터 시작하여 3개한 값에 1을 더하고 있다. 하지만 h의 초깃값이 지나치게 크면 효과가 없다. 따라서 배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 정해야 한다.
아래 프로그램은 이 방식의 수열을 사용하여 셸 정렬을 수행하는 프로그램이다.
# 셸 정렬 알고리즘 구현하기(h * 3 + 1의 수열 사용)
from typing import MutableSequence
def shell_sort(a: MutableSequence) -> None:
"""셸 정렬(h * 3 + 1의 수열 사용)"""
n = len(a)
h = 1
while h < n // 9:
h = h * 3 + 1
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 3
if __name__ == '__main__':
print('셸 정렬을 수행합니다(h * 3 + 1의 수열 사용).')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
shell_sort(x) # 배열 x를 셸 정렬
print(f'오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
셸 정렬을 수행합니다(h * 3 + 1의 수열 사용).
원소 수를 입력하세요.: 8
x[0]: 8
x[1]: 1
x[2]: 4
x[3]: 2
x[4]: 7
x[5]: 6
x[6]: 3
x[7]: 5
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8
Process finished with exit code 0
위 프로그램 중 첫번째 while문에서는 h의 초깃값을 구한다. 1부터 시작해서 h * 3 + 1의 수열을 사용하는 작업을 반복하지만 n // 9를 넘지 않는 최댓값을 h에 대입한다.
두 번째 반복문은 h값이 변하면서 h값을 3으로 나누는 작업을 반복해서 결국에 h값은 1이 된다.
셸 정렬의 시간 복잡도는 O(n^1.25)이고 단순 정렬의 시간 복잡도인 O(n^2)보다 매우 빠르다. 그러나 셸 정렬 알고리즘은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.