Cyclic Sort 간단히: 기본과 작동 원리 배우기
I’m happy to translate the article for you, but I’ll need the full text of the article (the portions you’d like translated) in order to do so. Could you please paste the content you want translated? Once I have that, I’ll keep the source link at the top unchanged and translate the rest into Korean while preserving all formatting, markdown, and code blocks.
Cyclic Sort
Cyclic sort는 **제자리(in‑place)**이며 불안정(unstable) 정렬 알고리즘으로, 요소가 1부터 N까지와 같이 알려진 범위에 있는 배열을 정렬하도록 특별히 설계되었습니다.
어떻게 동작하나요?
다음과 같은 배열을 오름차순으로 정렬하고 싶다고 가정합니다:
알고리즘은 반복적으로 요소를 선택하고 올바른 인덱스에 배치합니다.
첫 번째 요소(인덱스 0)부터 시작합니다.
-
첫 번째 요소 – 5 선택
올바른 인덱스는 4입니다(값 5는 위치 4에 있어야 함).
-
5와 인덱스 4에 있는 요소(값 2)를 교환
-
인덱스 0에 새로 들어온 요소 – 이제 2 확인
2는 인덱스 1에 있어야 하므로 올바른 위치에 있지 않습니다. 제어 변수는 진전하지 않습니다.
-
2와 인덱스 1에 있는 요소(값 4)를 교환
-
이제 인덱스 0에 있는 요소는 4
4는 인덱스 3에 있어야 하므로 아직 올바른 위치가 아닙니다.
-
4와 인덱스 3에 있는 요소(값 3)를 교환
-
이제 인덱스 0에 있는 요소는 3
3은 인덱스 2에 있어야 하므로 아직 올바른 위치가 아닙니다.
-
3과 인덱스 2에 있는 요소(값 1)를 교환
-
이제 인덱스 0에 있는 요소는 1 – 올바른 위치에 있습니다.
알고리즘은 제어 변수를 다음 인덱스(1)로 이동시키고 같은 과정을 반복합니다.(이미지 URL은 간결성을 위해 생략)
이 절차는 모든 요소가 자신의 올바른 인덱스에 배치될 때까지 계속되며, 최종적으로 정렬된 배열을 얻을 수 있습니다.
핵심 포인트
| Property | Description |
|---|---|
| In‑place | 추가 배열이 필요 없으며, 교환이 원본 배열 내에서 수행됩니다. |
| Unstable | 같은 값들의 상대적 순서는 보존되지 않습니다 (클래식 사용 사례는 서로 다른 값을 가짐). |
| Time Complexity | O(N) – 각 요소는 최대 한 번씩 올바른 위치로 이동합니다. |
| Space Complexity | O(1) – 몇 개의 보조 변수만 사용됩니다. |
| Ideal Input | 1 … N 정수(또는 인덱스로 매핑할 수 있는 연속된 범위)를 포함하는 배열. |
언제 사이클릭 정렬을 사용하나요
- 값의 범위를 미리 알 때 (예:
1..N의 순열). - O(1) 추가 공간으로 선형‑시간 정렬이 필요할 때.
- “누락된 숫자 찾기”, “중복 찾기”, 혹은 “각 요소를 올바른 인덱스에 배치하기”와 같은 문제에 활용.
💡 요소의 올바른 인덱스는 배열에 있는 숫자 범위가 1 부터 N까지일 경우 값 − 1이다.
공간 복잡도
이 알고리즘은 제자리 정렬 알고리즘이므로 보조 공간이 필요하지 않습니다. 따라서 공간 복잡도는 O(1) 입니다.
시간 복잡도
두 가지 시나리오가 있습니다: 최악의 경우와 최선의 경우.
최악의 경우
최악의 경우는 알려진 범위(예: 1 부터 N까지)를 가진 배열에서 모든 숫자가 잘못된 위치에 있을 때 발생합니다.
위에서 사용한 예시 배열, [5, 4, 1 (truncated).