이 글에서는 다음 문제 상황에 대한 해결 방법을 단계별로 살펴보겠습니다.
문제 정의
문제 — 하나의 배열이 주어졌을 때, 사이클 정렬(Cycle Sort) 개념을 활용하여 해당 배열을 정렬해야 합니다.
사이클 정렬은 제자리(in-place) 정렬 알고리즘입니다. 추가적인 메모리 없이 배열 내부에서 직접 정렬이 진행되며, 여러 개의 '사이클(cycle)'을 형성하면서 요소들이 교환(swap)되는 방식으로 동작합니다. 특히 사이클 정렬은 배열에 대한 쓰기(write) 연산 횟수를 이론상 최소화할 수 있어, 쓰기 비용이 큰 저장 장치(플래시 메모리, EEPROM 등)를 다룰 때 유용하게 활용됩니다.
사이클 정렬의 동작 원리
사이클 정렬은 다음과 같은 과정으로 진행됩니다.
- 현재 위치의 항목이 최종적으로 들어가야 할 올바른 위치를 계산합니다.
- 그 위치에 있던 기존 값을 꺼내고, 원래 항목을 그 자리에 놓습니다.
- 꺼낸 값에 대해 다시 같은 과정을 반복하며 하나의 사이클을 완성할 때까지 순환합니다.
- 모든 사이클이 처리되면 배열은 정렬된 상태가 됩니다.
이제 아래 구현 예제를 통해 실제 동작을 확인해 보겠습니다.
구현 예제
def cycleSort(array):
writes = 0
# 회전시켜야 할 사이클 탐색
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
# 항목이 놓일 위치 탐색
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# 이미 올바른 위치라면 새로운 사이클이 아님
if pos == cycleStart:
continue
# 중복 값 처리 후 항목 배치
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
# 사이클 회전 계속
while pos != cycleStart:
# 항목이 놓일 다음 위치 탐색
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# 항목 배치
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return writes
# main
arr = [1, 5, 3, 4, 8, 6, 3, 4, 5]
n = len(arr)
cycleSort(arr)
print("Sorted array is : ")
for i in range(0, n):
print(arr[i], end=" ")
실행 결과
Sorted array is : 1 3 3 4 4 5 5 6 8
모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 변수의 참조 관계는 위 코드 흐름에서 확인할 수 있습니다. 함수 마지막에는 배열에 실제로 발생한 쓰기 연산 횟수(writes)를 반환하므로, 정렬 과정에서 얼마나 적은 교환이 일어났는지도 측정할 수 있습니다.
시간 복잡도
- 최선 / 평균 / 최악: O(n²)
- 공간 복잡도: O(1) — 제자리 정렬로 추가 메모리가 거의 필요 없습니다.
사이클 정렬은 속도 면에서 퀵 정렬이나 병합 정렬보다 느리지만, 쓰기 연산 횟수를 최소화한다는 독특한 장점이 있습니다.
결론
이 글에서는 파이썬으로 사이클 정렬을 구현하는 방법을 알아보았습니다. 사이클을 형성하며 요소를 올바른 위치로 순환시키는 이 알고리즘은, 쓰기 연산을 줄여야 하는 특수한 상황에서 매우 효과적인 선택지가 됩니다. 예제 코드를 직접 실행하며 동작 원리를 익혀 보시기 바랍니다.