[Python] 셸 정렬

셸 정렬(Shell Sort): 삽입 정렬(Insertion Sort)의 단점을 보완하기 위해 고안된 정렬 알고리즘

📌 셸 정렬의 핵심 아이디어

삽입 정렬의 문제점

삽입 정렬은 거의 정렬된 상태에서는 빠르지만, 데이터가 멀리 떨어진 위치에서 교환이 필요하면 많은 이동이 발생하여 성능이 저하됨

셸 정렬의 해결법

배열을 일정한 간격(gap)으로 나누어 부분적으로 삽입 정렬을 수행함. 초기에는 큰 간격으로 정렬하여 원소들을 빠르게 "대략적인" 정렬 상태로 만들고, 점차 간격을 줄이며 최종적으로 정렬함

-> 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 단순 삽입 정렬보다 효율적임

from typing import MutableSequence

def shell_sort(a: MutableSequence) -> None:
  n = len(a)
  gap = n // 2
  while gap > 0:
    # gap만큼 떨어진 요소들을 삽입 정렬
    for i in range(gap, n):
      tmp = a[i]
      j = i
      while j >= gap and a[j - gap] > tmp:
        a[j] = a[j - gap]
        j -= gap
      a[j] = tmp
    gap //= 2

📌 분석

시간 복잡도

기본적인 셸 정렬 (단순 gap = n/2, n/4, ... 사용)이라면?

• 최악의 경우: O(n²) (삽입 정렬과 비슷한 성능)
• 평균적인 경우: 약 O(n^1.5)

그러나 Knuth 수열 등과 같이 어떤 gap으로 설정하는가에 따라 성능이 향상될 수도 있다.

불안정적

이웃하지 않고 떨어져 있는 원소를 서로 교환하기 때문에 안정적이지 않다.