C/C++로 구현하는 홀수-짝수 정렬(브릭 정렬) 완벽 가이드

홀수-짝수 정렬(Odd-Even Sort)은 브릭 정렬(Brick Sort)이라고도 불리며, 버블 정렬과 유사한 정렬 기법입니다. 이 정렬 방식은 홀수 단계(odd phase)와 짝수 단계(even phase)라는 두 개의 단계로 나뉘며, 모든 요소가 정렬될 때까지 매 반복마다 두 단계가 번갈아 수행됩니다.

동작 원리

홀수 단계는 버블 정렬처럼 동작하지만, 오직 홀수 인덱스에 있는 요소들만을 대상으로 비교와 교환을 수행합니다.

마찬가지로 짝수 단계는 짝수 인덱스에 있는 요소들만을 대상으로 정렬 작업을 진행합니다.

이 알고리즘은 병렬 처리(Parallel Processing)를 염두에 두고 설계된 간단한 정렬 기법입니다. 모든 홀수/짝수 인접 쌍에 대해 비교를 수행하며, 순서가 잘못된 쌍이 발견되면 이를 교환하여 올바른 순서로 만듭니다. 이 과정은 리스트 전체가 정렬될 때까지 반복됩니다.

병렬 프로세스용으로 개발된 만큼, 프로세서당 하나의 값을 할당하고 여러 프로세서가 비교-교환(compare-exchange) 연산을 동시에 수행할 수 있어 효율적입니다. 이 알고리즘은 원래 이러한 프로세서에서 효율적으로 동작하도록 제안되었습니다.

예제 입력 및 출력

입력: a[] = {3, 5, 7, 6, 1, 4, 2}
출력: 1 2 3 4 5 6 7

C 언어 구현 예제

#include <stdio.h>
#define MAX 7

void swap(int *, int *);
void oddeven_sort(int *);

int main() {
    int a[] = {3, 5, 7, 6, 1, 4, 2}, i;
    oddeven_sort(a);
    for (i = 0; i < MAX; i++) {
        printf(" %d", a[i]);
    }
    return 0;
}

void swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void oddeven_sort(int *x) {
    int sort = 0, i;
    while (!sort) {
        sort = 1;
        // 홀수 단계: 홀수 인덱스 요소들을 비교·교환
        for (i = 1; i < MAX; i += 2) {
            if (x[i] > x[i + 1]) {
                swap(&x[i], &x[i + 1]);
                sort = 0;
            }
        }
        // 짝수 단계: 짝수 인덱스 요소들을 비교·교환
        for (i = 0; i < MAX - 1; i += 2) {
            if (x[i] > x[i + 1]) {
                swap(&x[i], &x[i + 1]);
                sort = 0;
            }
        }
    }
}

코드 설명

oddeven_sort 함수는 sort 플래그 변수를 사용해 정렬 완료 여부를 판단합니다. 교환이 한 번이라도 일어나면 플래그가 0으로 설정되어 루프가 계속 반복되며, 더 이상 교환이 발생하지 않으면(플래그가 1로 유지되면) 정렬이 완료된 것으로 판단하고 종료합니다.

실행 결과

1 2 3 4 5 6 7