이 글에서는 브릭 정렬(Brick Sort), 즉 홀수-짝수 정렬(Odd-Even Sort)이 어떻게 동작하는지 살펴보겠습니다. 브릭 정렬은 버블 정렬(Bubble Sort)을 변형한 알고리즘으로, 전체 과정이 홀수 단계와 짝수 단계라는 두 부분으로 나뉩니다. 홀수 단계에서는 홀수 인덱스에 위치한 요소들에 버블 정렬을 적용하고, 짝수 단계에서는 짝수 인덱스의 요소들에 버블 정렬을 적용합니다. 이러한 과정을 배열이 완전히 정렬될 때까지 반복하며, 교환이 더 이상 일어나지 않으면 플래그(flag)를 통해 종료를 판단합니다.
병렬 처리 환경에서 각 인덱스 쌍의 비교가 서로 독립적으로 수행될 수 있어, 멀티코어 시스템에서 유용하게 활용되기도 하는 정렬 방식입니다.
알고리즘
brickSort(arr, n)
begin
flag := false
while the flag is not true, do
flag := true
for i := 1 to n-2, increase i by 2, do
if arr[i] > arr[i+1], then
exchange arr[i] and arr[i+1]
flag := false
end if
done
for i := 0 to n-2, increase i by 2, do
if arr[i] > arr[i+1], then
exchange arr[i] and arr[i+1]
flag := false
end if
done
done
end알고리즘 동작 순서
1. 플래그를 false로 초기화하고, 정렬이 완료될 때까지 반복문을 실행합니다.
2. 홀수 단계: 인덱스 1부터 시작해 2씩 증가시키며 인접한 요소 쌍(arr[i], arr[i+1])을 비교합니다. 앞의 값이 크면 두 요소를 교환하고 플래그를 false로 설정합니다.
3. 짝수 단계: 인덱스 0부터 시작해 2씩 증가시키며 같은 방식으로 비교와 교환을 수행합니다.
4. 한 번의 반복 동안 교환이 한 번도 일어나지 않았다면(플래그가 true로 유지된다면) 배열이 정렬된 것이므로 종료합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void brickSort(int arr[], int n){
bool flag = false;
while(!flag){
flag = true;
// 홀수 단계: 홀수 인덱스 요소들을 비교·교환
for(int i = 1; i<n-1; i = i+2){
if(arr[i] > arr[i+1]){
swap(arr[i], arr[i+1]);
flag = false;
}
}
// 짝수 단계: 짝수 인덱스 요소들을 비교·교환
for(int i = 0; i<n-1; i = i+2){
if(arr[i] > arr[i+1]){
swap(arr[i], arr[i+1]);
flag = false;
}
}
}
}
int main() {
int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
int n = sizeof(data)/sizeof(data[0]);
cout << "Sorted Sequence ";
brickSort(data, n);
for(int i = 0; i <n;i++){
cout << data[i] << " ";
}
}실행 결과
Sorted Sequence 13 20 32 35 40 54 74 98 98 154
정리
브릭 정렬은 버블 정렬과 마찬가지로 구현이 매우 간단하지만, 평균 및 최악의 경우 시간 복잡도는 O(n²)입니다. 다만 홀수 단계와 짝수 단계 내부의 비교 연산들이 서로 겹치지 않아 병렬화에 유리하다는 장점이 있으며, 이 때문에 '병렬 버블 정렬'이라고도 불립니다. 작은 규모의 데이터나 학습 목적의 예제로 활용하기에 적합한 알고리즘입니다.