Algorithm Guidecomplexity: O(n log² n)

쉘 정렬 (Shell Sort)

삽입 정렬을 일반화한 알고리즘으로, 간격(gap)을 점진적으로 줄이며 gapped insertion을 반복해 먼 거리의 원소를 효율적으로 이동시킵니다. 간격 수열에 따라 성능이 좌우됩니다.

01쉘 정렬 (Shell Sort)

알고리즘 작동 원리 탐색

쉘 정렬을 시작합니다. 멀리 떨어진 값끼리 먼저 맞바꿔 큰 흐트러짐을 걷어낸 뒤, 간격을 좁혀 가며 다듬습니다.

간격 4로 시작합니다. 네 칸 떨어진 값끼리 짝을 지어 네 쌍을 각각 정렬합니다.

첫 두 쌍은 45·67과 12·23 — 앞이 더 작아 이미 순서가 맞습니다.

세 번째 쌍은 89·56입니다. 순서가 뒤집혀 있어 네 칸 건너 자리를 맞바꿉니다.

네 번째 쌍 34·10도 뒤집혀 있습니다. 10을 앞으로 보내며 간격 4 단계를 마칩니다.

간격 4가 끝났습니다. 작은 값들이 앞쪽으로 크게 이동했습니다. 이제 간격을 2로 좁힙니다.

간격 2에서는 한 칸 건너뛴 값들이 두 그룹을 이룹니다. 그룹마다 삽입 정렬로 정리합니다.

두 번째 값부터 묶인 그룹에서 12와 10이 뒤집혀 있습니다. 두 칸 떨어진 자리끼리 맞바꿉니다.

간격 2가 끝났습니다. 배열이 제법 정돈됐습니다. 마지막으로 간격을 1로 좁힙니다.

간격 1은 보통의 삽입 정렬입니다. 45보다 작은 10과 12를 앞으로 옮깁니다.

23을 제자리에 끼워 넣습니다. 이미 거의 정렬돼 있어 옮기는 거리가 짧습니다.

마지막으로 34를 네 번째 자리에 끼워 넣으면 모든 값이 제자리를 찾습니다.

쉘 정렬이 끝났습니다. 미리 굵직하게 정돈해 둔 덕에 마지막 단계에서 옮길 일이 거의 없었습니다.

Live Python

1def shell_sort(arr):

# n: 8

2 n = len(arr)

# gap: 4

3 gap = n // 2

4 while gap > 0:

5 for i in range(gap, n):

6 temp = arr[i]

7 j = i

8 while j >= gap and arr[j - gap] > temp:

9 arr[j] = arr[j - gap]

10 j -= gap

11 arr[j] = temp

12 gap //= 2

13 return arr

1 / 13

02 쉽게 이해하기

For Everyone

🔑핵심 동작

멀리 떨어진 값끼리 먼저 맞추고 간격을 줄여 갑니다. 삽입 정렬이 값을 한 칸씩만 옮기는 한계를 넘습니다.

💡쉽게 말하면

일정 간격(gap)으로 떨어진 원소끼리 먼저 정렬하고, 간격을 줄여가며 마무리합니다.

삽입 정렬을 크게 개선했어요.

📍어디에 쓰나

–중간 규모 데이터
–메모리 제약 환경

03 파이썬 구현 코드

쉘 정렬 (Shell Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr