원 정렬(Circle Sort)이란?
원 정렬(Circle Sort)은 주어진 배열의 요소들을 정렬하는 독특하고 흥미로운 정렬 알고리즘입니다. 이 알고리즘은 배열의 요소들을 지름 방향, 즉 양 끝에서 서로 마주 보는 위치끼리 비교하며, 한쪽 부분의 정렬이 끝나면 계속해서 배열의 반대쪽 끝도 지름 방향으로 정렬해 나갑니다.
원 정렬 예시
예제 배열을 통해 원 정렬의 동작 과정을 시각화해 보겠습니다. 6개의 요소를 가진 배열이 있다고 가정합니다.
입력:
N = 6
arr[ ] = { 2, 1, 5, 8, 7, 9 }
각 배열 요소를 동심원 위에 배치하여 그려 보면 다음과 같습니다.
출력:
1 2 5 7 8 9
설명: 원 정렬을 사용해 배열의 요소들을 정렬하면 최종적으로 1, 2, 5, 7, 8, 9 순서가 됩니다.
원 정렬 알고리즘
- 배열의 첫 번째 요소와 마지막 요소를 비교하고, 두 번째 요소와 뒤에서 두 번째 요소를 비교하는 식으로 양 끝의 요소들을 짝지어 검사합니다.
- 배열을 두 개의 절반으로 나눈 뒤, 다시 원 정렬을 적용하여 첫 번째 절반의 첫 요소와 그 절반의 마지막 요소를 비교합니다.
- 배열 전체가 정렬될 때까지 위의 1~2단계를 재귀적으로 반복 호출합니다.
C++로 구현한 원 정렬 프로그램
#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
bool swaped = false;
if (n <= 2) {
if (arr[0] > arr[n - 1]) {
swap(arr[0], arr[n - 1]);
swaped = true;
}
return swaped;
}
int mid = (n + 1) / 2;
for (int i = 0; i < mid; i++) {
if (i == n - i - 1) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swaped = true;
}
} else {
if (arr[i] > arr[n - i - 1]) {
swap(arr[i], arr[n - i - 1]);
swaped = true;
}
}
}
if (circle_sort_rec(arr, mid))
swaped = true;
if (circle_sort_rec(arr + mid, n - mid))
swaped = true;
return swaped;
}
void circle_sort(int * arr, int size) {
while (circle_sort_rec(arr, size)) {
;
}
return;
}
int main() {
const int size = 6;
int arr[size] = {2, 1, 7, 4, 5, 9};
circle_sort(arr, size);
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
return 0;
}
실행 결과
1 2 4 5 7 9
코드 설명
- circle_sort_rec(): 배열의 지름 방향에 있는 요소들을 재귀적으로 비교하고, 필요하면 교환(swap)합니다. 교환이 한 번이라도 발생했는지 여부를 bool 값으로 반환합니다.
- circle_sort(): 더 이상 교환이 일어나지 않을 때, 즉 배열이 완전히 정렬될 때까지 circle_sort_rec()를 반복 호출합니다.
- main(): 예제 배열을 선언하고 원 정렬을 수행한 뒤, 정렬된 결과를 공백으로 구분하여 출력합니다.
시간 복잡도
원 정렬은 평균적으로 O(n log n) 수준의 비교 횟수를 보입니다. 다만 실무에서 널리 쓰이는 퀵 정렬이나 병합 정렬에 비해 성능상 이점은 크지 않으며, 주로 재귀적 사고방식을 익히거나 알고리즘 학습 목적으로 활용되는 알고리즘입니다.