셸 정렬
shell sort
는 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다.
- 단순 삽입 정렬은 다음의
장점
과단점
을 갖는다.
장점 : 이미 정렬을마쳤거나
거의끝나가는 상태
에서는 속도가 아주 빠르다.
단점 : 삽입할 위치가멀리 떨어져
있으면이동 횟수
가 많아진다.
셸 정렬
은 먼저 정렬할 배열의 원소를그룹으로 나눠
각 그룹별 정렬을 수행한다.그 후 정렬 된 그룹을
합치는 작업
을 반복하여 원소의 이동 횟수를 줄인다.1.시간 복잡도는 O(n^1.25)이지만 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.
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