선택 심화: Shell 정렬과 간격

떨어진 위치들의 삽입 정렬을 반복하고 간격 선택의 영향을 이해합니다.

이 장은 핵심 과정 뒤의 선택 심화입니다. Shell 정렬의 목표는 멀리 있는 값을 먼저 이동시켜 마지막 삽입 정렬의 부담을 줄이는 것입니다. 삽입 정렬을 이해한 뒤 읽으세요.

개념과 약속

간격 gap을 정하면 인덱스 나머지가 같은 위치들이 하나의 부분 수열입니다. gap=2에서는 0,2,4,…와 1,3,5,…를 각각 삽입 정렬합니다. 간격을 줄이다 마지막 gap=1에서 전체를 정렬합니다. 아래는 gap을 n//2부터 절반씩 줄이는 단순한 수열입니다.

간격 수열마다 성능 분석이 다릅니다. Shell 정렬이라는 이름만으로 한 시간 복잡도를 붙이지 않습니다. 먼 위치 이동으로 동률 항목의 순서를 바꿀 수 있어 일반적으로 안정적이지 않습니다. 부분 수열을 실제 새 목록으로 만들지 않고 같은 작업 목록의 떨어진 칸들을 이동합니다.

손으로 상태 추적하기

입력 [8,5,3,1,6,2]의 gap=3입니다.

위치 묶음	처음	간격 삽입 뒤
0,3	8,1	1,8
1,4	5,6	5,6
2,5	3,2	2,3

전체는 [1,5,2,8,6,3]입니다. gap을 1로 줄이면 전체 삽입 정렬로 끝냅니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def shell_sort(values):
    result = list(values)
    gap = len(result) // 2
    while gap:
        for i in range(gap, len(result)):
            current, j = result[i], i
            while j >= gap and result[j - gap] > current:
                result[j] = result[j - gap]
                j -= gap
            result[j] = current
        gap //= 2
    return result


print(shell_sort([8, 5, 3, 1, 6, 2]))
print(shell_sort([2, 2, 1]))
print(shell_sort([]))