개요
버블 정렬이나 삽입 정렬이 수행되는 과정을 살펴보면, 이웃하는 원소의 숫자들끼리 자리를 이동함으로써 정렬이 이루어진다.
버블 정렬
버블 정렬의 경우, 가장 작은 숫자 1이 배열의 앞부분으로 매우 느리게 이동하는 것을 알 수 있다.
삽입 정렬
삽입 정렬에서 만약 배열의 마지막 원소가 가장 작은 숫자라면, 그 숫자가 맨 앞으로 이동해야 하므로, 모든 다른 숫자들은 1칸씩 오른쪽으로 이동해야 한다.
쉘 정렬(Shell Sort)은 이러한 단점을 보완하기 위해서 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고. 동시의 앞부분의 큰 숫자는 뒷부분으로 이동시키며, 가장 마지막에서는 삽입 정렬을 수행한다.
예제
다음 배열을 쉘 정렬을 사용해 정렬하시오
[30,60,90,10,40,80,40,20,10,60,50,30,40,90,80]
- 먼저 간격(gap)이 5가 되는 숫자끼리 그룹을 만든다, 총 15개의 숫자가 있으므로
첫 번째 그룹은 [30,80,50]
두 번째 그룹은 [60,40,30]
세 번째 그룹은 [90,20,40]
네 번째 그룹은 [10,10,90]
다섯 번째 그룹은 [40,60,80] 이다.
이후 그룹별로 삽입 정렬을 수행한다.
간격(gap)이 5인 그룹별로 정렬한 결과를 살펴보면, 80과 90같은 큰 숫자가 뒷부분으로 이동하였고, 20, 30과 같은 작은 숫자가 앞부분으로 한번에 이동한 것을 볼 수 있다.
- 그 다음에는 간격을 5보다 작게 하여, 예를 들어 3으로 하여, 3개의 그룹으로 나누어 각 그룹별로 삽입 정룔을 수행한다.
첫 번째 그룹은[30,10,40,60,90]
두 번째 그룹은[30,40,40,80,90]
세 번째 그룹은[10.20.50.60.80]
마지막으로 간격을 1로 놓고 삽입 정렬을 수행한다. 쉘 정렬의 마지막 간격(gap)은 무조건 1이어야 하는데 왜냐하면 다른 그룹에 속하여 서로 비교되지 않은 숫자가 있을 수 있기 때문이다. 따라서 마지막 단계는 삽입정렬 그 자체를 수행하는 것이라고 볼 수 있다.
코드
### 삽입 정렬 함수
def gapInsertionSort(x, start, gap):
for target in range(start+gap, len(x), gap):
#비교하고자 하는 숫자
val = x[target]
#비교하고자 하는 숫자의 인덱스
i = target
while i > start:
if x[i-gap]> val:
x[i] = x[i-gap]
else:
break
i -= gap
x[i] = val
def shellSort(x):
# 첫번째 간격을 설정 (총 전체 배열 길이의 반으로)
gap = len(x) // 2
while gap > 0:
for start in range(gap):
gapInsertionSort(x, start, gap)
#간격을 점점 줄여나간다
gap = gap // 2
return x정리
쉘 정렬의 수행 속도는 간격 선정에 따라 좌우된다. 지금까지 알려진 가장 좋은 성능을 보이는 간격은 1, 4, 10, 23, 57, 132, 301, 701이고 701이후는 아직 밝혀지지 않았다고 한다. 이 때문에 쉘 정렬의 시간복잡도 또한 아직 풀리지 않은 문제로 남아있다.
쉘 정렬을 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보이는데, 쉘 정렬의 특유의 간격을 사용한 정렬 방식은 특징이 입베디드 시스템에서 하드웨어로 정렬 알고리즘을 구현하는데 매우 적합하다고 한다.
출처 : 알기쉬운 알고리즘 양성봉 저
