배처 홀짝 병합 정렬

1. 개요

배처 홀짝 병합 정렬은 2의 거듭제곱 길이를 가진 리스트를 정렬하는 알고리즘이다. 파이썬으로 구현된 예시 코드를 통해 작동 방식을 확인할 수 있으며, 병합 정렬 방식을 사용한다.

2. 알고리즘

배처 홀짝 병합 정렬은 병합 정렬의 일종으로, 재귀적인 방식으로 리스트를 정렬한다. 기본적인 아이디어는 리스트를 반으로 나누어 각각 정렬한 다음, '홀짝 병합(odd-even merge)'이라는 특별한 방식으로 두 정렬된 부분을 합치는 것이다.

이 알고리즘은 비교 및 교환(compare-and-swap) 연산을 기반으로 한다. 두 요소의 위치를 비교하여 필요한 경우 서로 바꾸는 간단한 연산이다.

다음은 파이썬으로 구현된 배처 홀짝 병합 정렬 알고리즘의 예시이다. 입력 리스트 `x`는 0부터 인덱싱된다고 가정한다.


def compare_and_swap(x, a, b):
""" 배열 x의 a와 b 인덱스 요소를 비교하여, x[a] > x[b] 이면 두 요소의 위치를 바꾼다. """
if x[a] > x[b]:
x[a], x[b] = x[b], x[a]

def oddeven_merge(x, lo, hi, r):
""" 홀짝 병합을 수행하는 함수. lo부터 hi까지 r 간격으로 요소를 비교하고 교환한다. """
step = r * 2
if step < hi - lo:
# 병합 단계를 재귀적으로 더 작은 부분 문제로 나눈다.
oddeven_merge(x, lo, hi, step) # 짝수 인덱스 부분 병합 (간격 step)
oddeven_merge(x, lo + r, hi, step) # 홀수 인덱스 부분 병합 (간격 step)
# 부분 병합 결과를 합친다. (간격 r)
for i in range(lo + r, hi - r, step):
compare_and_swap(x, i, i + r)
else:
# 가장 작은 단위의 병합 (요소 2개 비교, 간격 r)
compare_and_swap(x, lo, lo + r)

def oddeven_merge_sort_range(x, lo, hi):
""" 배열 x의 lo부터 hi까지 구간을 정렬한다. (lo와 hi 인덱스 포함) """
if (hi - lo) >= 1:
# 구간에 요소가 1개 이상 있을 경우
# 구간을 반으로 나누어 각각 재귀적으로 정렬한다.
mid = lo + ((hi - lo) // 2) # 중간 인덱스 계산 (정수 나눗셈)
oddeven_merge_sort_range(x, lo, mid) # 앞부분 정렬
oddeven_merge_sort_range(x, mid + 1, hi) # 뒷부분 정렬
# 정렬된 두 부분을 홀짝 병합한다. (초기 간격 1)
oddeven_merge(x, lo, hi, 1)

def oddeven_merge_sort(x):
""" 입력 리스트 x 전체를 배처 홀짝 병합 정렬한다. """
oddeven_merge_sort_range(x, 0, len(x)-1)

# 실행 예시
data = [2, 4, 3, 5, 6, 1, 7, 8]
oddeven_merge_sort(data)
# 정렬 후 data: [1, 2, 3, 4, 5, 6, 7, 8]


위 코드에서 `oddeven_merge_sort_range` 함수는 리스트를 재귀적으로 반으로 나누어 정렬하고, `oddeven_merge` 함수를 호출하여 정렬된 두 부분을 병합한다. `oddeven_merge` 함수는 홀수 위치와 짝수 위치의 요소들을 비교하는 과정을 재귀적으로 반복하여 전체 구간을 정렬된 상태로 만든다.

비교 및 정렬할 요소의 인덱스를 계산하는 구체적인 방법은 의사 코드 섹션에서 자세히 설명한다. 파트너 노드 인덱스를 재귀 없이 계산하는 방법도 존재한다.

2.1. 의사 코드

다음은 배처 홀짝 병합 정렬 알고리즘의 의사 코드이다. 입력 배열은 0부터 n-1까지 인덱싱된다고 가정한다.


# 참고: 입력 시퀀스는 0부터 (n-1)까지 인덱싱됩니다.
for p = 1, 2, 4, 8, ... # p < n인 동안
for k = p, p/2, p/4, p/8, ... # k >= 1인 동안
for j = mod(k,p) to (n-1-k) with a step size of 2k
for i = 0 to k-1 with a step size of 1
if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))
# 요소 (i+j)와 (i+j+k)를 비교하고 정렬합니다.
compare_and_swap(sequence[i+j], sequence[i+j+k])


비교 및 정렬할 요소의 인덱스를 계산하는 데에는 다양한 재귀 및 반복 방식이 사용될 수 있다. 다음은 n개의 요소를 정렬하기 위한 인덱스를 생성하는 반복 기법 중 하나이다.


# 참고: 입력 시퀀스는 0부터 (n-1)까지 인덱싱됩니다.
for p = 1, 2, 4, 8, ... # p < n인 동안
for k = p, p/2, p/4, p/8, ... # k >= 1인 동안
for j = mod(k,p) to (n-1-k) with a step size of 2k
for i = 0 to min(k-1, n-j-k-1) with a step size of 1
if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))
# 요소 (i+j)와 (i+j+k)를 비교하고 정렬합니다.
compare_and_swap(sequence[i+j], sequence[i+j+k])


파트너 노드 인덱스를 재귀 없이 계산하는 것도 가능하다.

3. 구현 예시

배처 홀짝 병합 정렬 알고리즘은 다양한 프로그래밍 언어로 구현될 수 있다. 대표적인 예시 중 하나로 파이썬을 이용한 구현이 있으며, 이는 입력으로 길이가 2의 거듭제곱인 리스트를 받아 정렬된 리스트를 반환하는 방식으로 동작한다.

3.1. Python

다음은 Python으로 구현된 배처 홀짝 병합 정렬 코드이다. 이 코드는 입력으로 길이가 2의 거듭제곱인 리스트를 받아 정렬된 리스트를 반환한다.


def compare_and_swap(x, a, b):
"""리스트 x의 a, b 인덱스 요소를 비교 후 교환"""
if x[a] > x[b]:
x[a], x[b] = x[b], x[a]

def oddeven_merge(x, lo, hi, r):
"""홀짝 병합 수행 (재귀 호출 가능)"""
step = r * 2
if step < hi - lo:
oddeven_merge(x, lo, hi, step)
oddeven_merge(x, lo + r, hi, step)
# 병합 단계: r 간격의 요소들을 비교/교환
for i in range(lo + r, hi - r, step):
compare_and_swap(x, i, i + r)
else:
# 기본 단계: 인접한 요소 비교/교환
compare_and_swap(x, lo, lo + r)

def oddeven_merge_sort_range(x, lo, hi):
""" 리스트 x의 lo부터 hi까지 구간 정렬 (lo, hi 인덱스 포함)"""
if (hi - lo) >= 1:
# 구간에 요소가 1개 이상일 경우
# 구간을 절반으로 나누어 각각 재귀 정렬 후 병합
mid = lo + ((hi - lo) // 2) # 정수 나눗셈
oddeven_merge_sort_range(x, lo, mid)
oddeven_merge_sort_range(x, mid + 1, hi)
oddeven_merge(x, lo, hi, 1)

def oddeven_merge_sort(x):
"""리스트 x 전체를 배처 홀짝 병합 정렬"""
oddeven_merge_sort_range(x, 0, len(x)-1)

# 실행 예시
data = [2, 4, 3, 5, 6, 1, 7, 8]
oddeven_merge_sort(data)
# 정렬 후 data: [1, 2, 3, 4, 5, 6, 7, 8]