정의

사이클 정렬은 값이 1~n인 배열에서 각 값이 가야 할 자리(인덱스 = 값 - 1)가 정해져 있다는 사실을 이용합니다. 현재 보는 값이 제자리가 아니면 그 값을 곧장 집(home)으로 보내고, 제자리면 다음으로 넘어갑니다.

핵심 특성

• ✓값 1~n과 인덱스의 1:1 대응을 이용 - 값 v의 집은 항상 인덱스 v-1
• ✓각 값은 한 번만 제자리로 이동 - 전체 교환 횟수가 n 이하라 O(n)
• ✓제자리 정렬 - 추가 메모리 없이 배열 안에서 교환만으로 정렬
• ✓불안정 정렬이며 값 범위가 1~n으로 제한될 때만 사용 가능

시간 복잡도