이 글에서는 홀짝 정렬(Odd-Even Sort), 즉 브릭 정렬(Brick Sort) 알고리즘을 파이썬으로 구현하는 방법을 단계별로 알아보겠습니다.
문제 정의
주어진 배열을 브릭 정렬 알고리즘을 이용해 오름차순으로 정렬하는 것이 목표입니다.
홀짝 정렬의 동작 원리
홀짝 정렬은 버블 정렬(Bubble Sort)의 변형 알고리즘으로, 두 개의 단계를 번갈아 가며 반복 실행합니다.
- 홀수 단계(Odd Phase): 홀수 인덱스에 위치한 요소들을 대상으로 버블 정렬을 수행합니다. 즉, 인덱스 1과 2, 3과 4처럼 인접한 쌍을 비교하여 필요하면 교환합니다.
- 짝수 단계(Even Phase): 짝수 인덱스에 위치한 요소들을 대상으로 버블 정렬을 수행합니다. 인덱스 0과 1, 2와 3의 쌍을 비교·교환합니다.
이 두 단계를 배열 전체가 정렬될 때까지, 즉 더 이상 교환이 일어나지 않을 때까지 반복합니다. 각 단계에서 서로 겹치지 않는 쌍들을 동시에 비교할 수 있기 때문에 병렬 처리에 적합하다는 점이 이 알고리즘의 큰 장점입니다.
구현 예제
def oddEvenSort(arr, n):
# 정렬 완료 여부를 나타내는 플래그
isSorted = 0
while isSorted == 0:
isSorted = 1
temp = 0
# 홀수 단계: 홀수 인덱스 요소들에 대해 버블 정렬 수행
for i in range(1, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
isSorted = 0
# 짝수 단계: 짝수 인덱스 요소들에 대해 버블 정렬 수행
for i in range(0, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
isSorted = 0
return
arr = [1, 4, 2, 3, 6, 5, 8, 7]
n = len(arr)
oddEvenSort(arr, n)
print("정렬된 배열:")
for i in range(0, n):
print(arr[i], end=" ")실행 결과
정렬된 배열: 1 2 3 4 5 6 7 8
코드 설명
위 코드에서 모든 변수는 지역 범위(local scope) 내에서 선언되며, 동작 방식은 다음과 같습니다.
isSorted플래그는 현재 패스에서 교환이 발생했는지를 추적합니다. 교환이 한 번이라도 일어나면 0으로 설정되어 루프가 다시 반복됩니다.- 홀수 단계와 짝수 단계가 각각 한 번씩 실행된 후에도 교환이 없었다면, 배열은 완전히 정렬된 상태이므로 루프가 종료됩니다.
- 파이썬의 튜플 언패킹(
arr[i], arr[i+1] = arr[i+1], arr[i])을 활용해 임시 변수 없이 깔끔하게 두 요소를 교환할 수 있습니다.
시간 복잡도
홀짝 정렬의 평균 및 최악의 경우 시간 복잡도는 O(n²)로 버블 정렬과 동일하지만, 비교 연산이 독립적으로 수행될 수 있어 멀티코어·분산 환경에서 병렬화했을 때 효율을 크게 높일 수 있습니다.
결론
이번 글에서는 파이썬으로 홀짝 정렬(브릭 정렬)을 구현하는 방법을 살펴보았습니다. 버블 정렬을 확장한 개념으로 코드가 단순하면서도 병렬 처리에 유리한 특성이 있어, 정렬 알고리즘의 기본기를 익히고 병렬 컴퓨팅 개념을 학습하기에 좋은 예제입니다.