삽입 정렬은 어느정도 정렬된 리스트에서 매우 빠르다. 이것에서 착안된 것이 쉘정렬이다.
- 삽입 정렬은 요소들이 이웃 위치로만 이동하므로, 많은 이동이 필요하다.
- 요소들이 멀리 떨어진 위치로 이동할 수 있다면 보다 적게 이동하여 제자리를 찾을 수 있다.
방법
- 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눈다.
- 나뉘어진 각각의 부분 리스트를 삽입 정렬
- 간격을 줄임
- 부분 리스트의 수는 작아지고 각 부분 리스트의 크기는 더 커진다
- 간격이 1이 될 때까지 부분 리스트의 삽입 정렬 과정 반복
-> 수행시간은 간격에 따라 달라지며 입력이 크지 않을 때 성능이 Good
def shell_sort(inp):
h = len(inp)//2
while h > 0:
for i in range(h, len(inp):
t = inp[i]
j = i
while( j >= h and inp[i-h] > t: #삽입정렬
inp[j] = inp[j-h]
j -= h
inp[j] = t
h = h//2- 원거리 자료이동을 통해 위치 교환 횟수를 줄여준다
- 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입 정렬 속도 증가
시간 복잡도
- 최악 : O(n^2)
- 평균 : O(n^1.5)
