Shell Sort 구현: 이론에서 실용 코드까지

Source: Dev.to

쉘 정렬이란?

쉘 정렬은 기본적인 정렬 알고리즘 중 하나인 삽입 정렬을 개선한 방식입니다. 삽입 정렬은 주어진 배열에서 인접한 요소들을 비교하고 삽입합니다.
반면에 쉘 정렬은 고정된 간격(gap)으로 떨어진 요소들에 대해 삽입과 유사한 연산을 반복 수행하며, 간격을 점차 줄여갑니다. 간격이 1이 되면 알고리즘은 삽입 정렬과 동일하게 동작합니다.

이것은 중요한 질문을 제기합니다: 쉘 정렬이 결국 삽입 정렬이 된다면, 개선 효과는 어디에서 오는 걸까요?

복잡도 개요

• 삽입 정렬

  • 시간 복잡도: (O(n^2)) ~ (O(n))
  • 공간 복잡도: (O(1))

• 쉘 정렬 (간격 순서에 따라)

  • 시간 복잡도: 대략 (O(n^{1.3})) ~ (O(n \log n))
  • 공간 복잡도: (O(1))

실제로는 입력 크기가 약 1,000 개 정도를 넘어설 때 성능 차이가 눈에 띕니다.

예시 문제

점수가 무작위로 배치된 10,000명의 엔지니어 점수가 주어졌을 때, 점수가 비슷한 엔지니어들을 짝지어야 합니다.

1. 엔지니어들을 점수 순으로 정렬합니다.
2. 정렬된 리스트에서 인접한 요소들을 짝지습니다.

1단계에 삽입 정렬을 사용하면 최악의 경우 10억 번에 달하는 연산이 필요할 수 있습니다 ((O(n^2))). 쉘 정렬은 간격 순서에 따라 평균 시간을 대략 (O(n^{1.3})) ~ (O(n \log n)) 수준으로 줄여줍니다.

삽입 정렬 접근법

인덱스 (i)를 1 부터 (n-1)까지 반복합니다:

1. A_i의 값을 임시 변수 x에 저장합니다.
2. (A_j > x)인 동안 ((j = i-1, i-2, \dots)) A_j를 한 칸 오른쪽으로 이동시킵니다.
3. x를 올바른 위치에 삽입합니다.

삽입 정렬은 간격 크기가 1인 경우의 쉘 정렬이라고 볼 수 있습니다.

쉘 정렬 접근법

1. 초기 간격 값 g를 선택합니다.
2. 인덱스 (i)를 g부터 (n-1)까지 반복합니다:
   • A_i를 임시 변수 x에 저장합니다.
   • (A_j > x)인 동안 ((j = i-g, i-2g, \dots)) A_j를 A_{j+g}로 이동시킵니다.
   • x를 A_{j+g}에 삽입합니다.
3. 간격을 줄이고 2‑3단계를 반복합니다. 간격이 1이 될 때까지 진행합니다.

쉘 정렬 구현

패턴 1: 입력으로 간격 순서가 제공되는 경우

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        # Store the value of A[i] in a temporary variable x
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            # Shift A[j] to A[j+gap]
            array[j + gap] = array[j]
            j -= gap
        # Insert x into A[j+gap]
        array[j + gap] = x

def shell_sort(array, n, gap_sequence):
    for gap in gap_sequence:
        insertion_sort(array, n, gap)

n은 배열의 요소 개수를 나타냅니다.

패턴 2: 알고리즘 내부에서 간격 순서를 생성하는 경우

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            array[j + gap] = array[j]
            j -= gap
        array[j + gap] = x

def shell_sort(array, n):
    # Create the gap sequence (using the classic n//2, n//4, …, 1 scheme)
    gap_sequence = []
    gap = n // 2
    while gap > 0:
        gap_sequence.append(gap)
        gap //= 2
    if not gap_sequence:
        gap_sequence.append(1)

    for gap in gap_sequence:
        insertion_sort(array, n, gap)

쉘 정렬에 대한 최적의 간격 순서는 아직도 미해결 문제입니다. 오류가 발견되면 언제든 알려 주세요.