Algorithm Guidecomplexity: O(n log² n)

쉘 정렬 (Shell Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Shell Sort · gap=4→2→1

쉘 정렬을 시작합니다. 간격(gap)을 줄여가며 간격을 둔 삽입 정렬을 반복합니다. n=8, gap = n/2 = 4.

Logic Node1 / 13

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

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

Guide Progress0%