순환 정렬(Cycle Sort)을 위한 C++ 프로그램

순환 정렬(Cycle Sort)은 제자리(in-place) 정렬이면서 불안정(unstable)한 비교 기반 정렬 알고리즘입니다. 다른 어떤 제자리 정렬 알고리즘과 달리, 원본 배열에 수행되는 쓰기(write) 연산의 총 횟수가 이론적으로 최적(optimal)이라는 점이 가장 큰 특징입니다.

순환 정렬의 핵심 아이디어는 다음과 같습니다. 정렬해야 할 순열(permutation)은 여러 개의 사이클(cycle)로 분해할 수 있으며, 각 사이클을 개별적으로 회전시키면 정렬된 결과를 얻을 수 있습니다.

순환 정렬의 핵심 특징

거의 모든 다른 정렬 알고리즘과 달리, 순환 정렬에서는 요소를 단순히 자리를 비우기 위해 배열의 다른 곳에 임시로 옮겨 적는 작업을 하지 않습니다. 각 값은 다음 두 경우 중 하나로만 처리됩니다.

이미 올바른 위치에 있다면 0번 기록됨
올바른 위치가 아니라면 딱 한 번 해당 위치에 1번 기록됨

이는 제자리 정렬을 완료하는 데 필요한 최소한의 덮어쓰기(overwrite) 횟수와 정확히 일치합니다.

쓰기 횟수를 최소화하는 것이 중요한 이유

대용량 데이터셋에 대한 쓰기 작업 비용이 매우 클 때 이 특성이 빛을 발합니다. 대표적인 예가 플래시 메모리 같은 EEPROM입니다. 플래시 메모리는 쓰기 작업이 발생할 때마다 메모리 수명이 줄어들기 때문에, 쓰기 횟수를 최소화하는 순환 정렬이 실질적인 이점을 제공합니다.

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

동작 원리 설명

배열 arr[] = {10, 5, 2, 3}을 예로 들어 사이클 시작 인덱스가 0일 때의 과정을 살펴보겠습니다.

arr[] = {10, 5, 2, 3}
index = 0 1 2 3
cycle_start = 0
item = 10 = arr[0]

① item(10)이 들어갈 위치를 찾습니다.
   pos = cycle_start
   while (arr[i] < item)
       pos++;

② 10을 arr[3]에 넣고, item을 arr[3]의 기존 값으로 갱신합니다.
   arr[] = {10, 5, 2, 10}
   item = 3

③ 인덱스 '0'에서 시작하는 나머지 사이클을 다시 회전합니다.
   item = 3이 들어갈 위치를 찾아 arr[1]과 교환합니다.
   arr[] = {10, 3, 2, 10}
   item = 5

④ 다시 사이클을 회전하며 item = 5를 arr[2]와 교환합니다.
   arr[] = {10, 3, 5, 10}
   item = 2

⑤ 마지막으로 item = 2를 제자리에 놓으면 사이클이 닫힙니다.
   arr[] = {2, 3, 5, 10}

위 과정은 cycle_start = 0일 때의 한 번의 반복입니다. 이후 cycle_start = 1, 2, ... n-2에 대해 동일한 단계를 반복하면 전체 배열이 정렬됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void cycleSort(int a[], int n) {
    int writes = 0;
    for (int c_start = 0; c_start <= n - 2; c_start++) {
        int item = a[c_start];
        int pos = c_start;
        // item보다 작은 요소의 개수만큼 위치를 이동
        for (int i = c_start + 1; i < n; i++)
            if (a[i] < item)
                pos++;
        // 이미 올바른 위치에 있으면 건너뜀
        if (pos == c_start)
            continue;
        // 중복 요소는 건너뛰고 다음 위치로 이동
        while (item == a[pos])
            pos += 1;
        if (pos != c_start) {
            swap(item, a[pos]);
            writes++;
        }
        // 현재 사이클이 닫힐 때까지 회전 반복
        while (pos != c_start) {
            pos = c_start;
            for (int i = c_start + 1; i < n; i++)
                if (a[i] < item)
                    pos += 1;
            while (item == a[pos])
                pos += 1;
            if (item != a[pos]) {
                swap(item, a[pos]);
                writes++;
            }
        }
    }
}

int main() {
    int a[] = {7, 4, 3, 5, 2, 1, 6};
    int n = 7;
    cycleSort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

실행 결과

1 2 3 4 5 6 7

복잡도 분석

시간 복잡도: 최선·평균·최악의 경우 모두 O(n²)
공간 복잡도: O(1) — 추가 메모리가 거의 필요 없는 제자리 정렬
쓰기 횟수: 최대 n번 — 이론상 최소치로, 쓰기 비용이 큰 환경(EEPROM, 플래시 메모리 등)에 적합

정리하면, 순환 정렬은 일반적인 상황에서는 O(n²)의 시간 복잡도 때문에 느린 편이지만, 메모리 쓰기 횟수를 극한까지 줄여야 하는 특수한 환경에서는 매우 유용하게 활용할 수 있는 알고리즘입니다.