순환 정렬(Cycle Sort)이란?
순환 정렬(Cycle Sort)은 제자리(in-place) 정렬 알고리즘의 하나로, 각 원소를 자신이 위치해야 할 곳으로 직접 옮기는 '사이클' 단위로 배열을 정렬하는 방식입니다. 비교 기반(comparison-based) 정렬에 속하며, 가장 큰 특징은 정렬 과정에서 발생하는 메모리 쓰기(write) 연산 횟수를 이론상 최소한으로 줄인다는 점입니다.
이러한 특성 때문에 순환 정렬은 쓰기 작업 비용이 큰 환경에서 특히 유용합니다. 대표적으로 EEPROM이나 플래시 메모리처럼 쓰기 횟수가 수명에 직결되는 저장 장치에서 데이터를 정렬할 때 활용 가치가 높습니다.
순환 정렬의 복잡도
- 시간 복잡도: O(n²)
- 공간 복잡도: O(1)
시간 복잡도는 최선·평균·최악의 경우 모두 O(n²)로 버블 정렬이나 선택 정렬과 유사하지만, 쓰기 연산 횟수는 최대 n번으로 제한되어 쓰기 비용이 지배적인 상황에서는 오히려 가장 효율적인 선택이 될 수 있습니다.
입력 및 출력 예시
입력:
정렬되지 않은 데이터 목록: 23 63 98 74 20 14 36 45 99 78
출력:
정렬 전 배열: 23 63 98 74 20 14 36 45 99 78
정렬 후 배열: 14 20 23 36 45 63 74 78 98 99
알고리즘 동작 원리
함수 시그니처는 다음과 같습니다.
cycleSort(array, size)
입력 − 정렬할 데이터 배열과 배열의 전체 원소 개수
출력 − 정렬이 완료된 배열
순환 정렬의 핵심 로직은 다음과 같습니다.
- 현재 위치(start)의 값을 key로 가져옵니다.
- key보다 작은 원소가 오른쪽에 몇 개 있는지 세어, key가 들어가야 할 최종 위치(location)를 계산합니다.
- 계산된 위치에 이미 같은 값이 있다면 중복을 피하기 위해 위치를 한 칸 뒤로 밀어냅니다.
- key를 해당 위치의 값과 교환하고, 빼돌린 값을 다시 올바른 위치로 옮기는 과정을 사이클이 시작 위치로 돌아올 때까지 반복합니다.
Begin
for start := 0 to n – 2 do
key := array[start]
location := start
for i := start + 1 to n-1 do
if array[i] < key then
location := location + 1
done
if location = start then
이미 올바른 위치이므로 다음 반복으로 진행
while key = array[location] do
location := location + 1 // 중복 값 처리
done
if location ≠ start then
array[location]과 key를 교환
while location ≠ start do
location := start
for i := start + 1 to n-1 do
if array[i] < key then
location := location + 1
done
while key = array[location]
location := location + 1
if key ≠ array[location]
array[location]과 key를 교환
done
done
End
C++ 구현 예제
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { // a와 b의 값을 서로 교환
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void cycleSort(int *array, int n) {
for(int start = 0; start<n-1; start++) { // 각 원소를 올바른 위치에 배치
int key = array[start];
int location = start;
for(int i = start+1; i<n; i++) { // key보다 작은 원소의 개수를 세어 위치 계산
if(array[i] < key)
location++;
}
if(location == start) // 이미 올바른 위치라면 다음 반복으로 진행
continue;
while(key == array[location]) // 동일한 값이 있으면 위치를 한 칸 뒤로 이동
location++;
if(location != start)
swapping(array[location], key);
while(location != start) {
location = start;
for(int i = start+1; i<n; i++) { // 원소를 넣을 위치 탐색
if(array[i] < key)
location++;
}
while(key == array[location]) // 동일한 값이 있으면 위치를 한 칸 뒤로 이동
location++;
if(key != array[location])
swapping(key, array[location]);
}
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
cycleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
실행 결과
Enter the number of elements: 10
Enter elements:
23 63 98 74 20 14 36 45 99 78
Array before Sorting: 23 63 98 74 20 14 36 45 99 78
Array after Sorting: 14 20 23 36 45 63 74 78 98 99
마무리
순환 정렬은 일반적인 정렬 상황에서는 O(n²)의 시간 복잡도로 인해 퀵 정렬이나 병합 정렬보다 성능이 떨어지지만, 쓰기 연산 횟수를 최소화해야 하는 특수한 환경에서는 대체하기 어려운 강점을 가진 알고리즘입니다. 각 원소가 정확히 한 번씩 최종 위치에 기록된다는 점을 기억해 두면, 메모리 쓰기 비용이 중요한 시스템을 설계할 때 큰 도움이 될 것입니다.