정렬 알고리즘 (Sorting Algorithms) - 사이클 정렬 (Cycle Sort)

사이클 정렬 (Cycle Sort)

사이클 정렬 (Cycle Sort)은 최소한의 데이터를 이동시키면서 정렬을 수행하는 비교 기반 정렬 알고리즘입니다. 주로 공간 효율성과 데이터 이동 횟수 최소화를 목적으로 설계되었습니다. 이 정렬 알고리즘은 제자리 정렬 (in-place sorting)이며, 데이터 이동 횟수를 최소화하기 때문에 쓰기 작업이 제한된 환경에서 유용합니다.

---

1. 작동 원리

1. 배열의 각 요소는 정렬된 상태에서 자신이 있어야 할 위치를 찾아서 이동합니다. 이 과정은 "사이클"이라 불립니다.
2. 데이터의 현재 위치와 최종 위치가 다르면, 두 위치를 교환하여 해당 데이터를 올바른 위치로 이동시킵니다.
3. 데이터가 제자리를 찾으면, 다음 데이터를 처리하며 이를 배열 전체에 대해 반복합니다.

---

2. 알고리즘의 특징

• 시간 복잡도:
  • 최선, 평균, 최악: O(n^2)
  • 데이터의 이동 횟수는 최소화되므로 효율적이나, 비교 횟수는 많아질 수 있습니다.
• 공간 복잡도:
  • 제자리 정렬로 추가 메모리 사용량은 O(1)입니다.
• 안정성:
  • 불안정 정렬로, 같은 값의 데이터 순서가 변경될 수 있습니다.

---

3. 사이클 정렬 과정

정렬되지 않은 배열: [4, 3, 2, 1]

1. 첫 번째 요소 (4):
   • 4의 최종 위치를 확인 → (4보다 작은 요소의 개수를 카운트) → 위치는 3번 인덱스.
   • 4를 위치 3번으로 이동 → [1, 3, 2, 4].
2. 두 번째 요소 (1):
   • 1의 최종 위치를 확인 → 위치는 0번 인덱스.
   • 1을 위치 0번으로 이동 → [1, 3, 2, 4].
3. 세 번째 요소 (3):
   • 3의 최종 위치를 확인 → 위치는 2번 인덱스.
   • 3을 위치 2번으로 이동 → [1, 2, 3, 4].
4. 마지막 요소는 이미 제자리에 있음.

---

4. 장점과 단점

장점:

• 쓰기 횟수 최소화: 배열 내 데이터 이동 횟수를 최소화합니다. 이 특성 때문에 쓰기 작업이 비싼 저장 매체(예: 플래시 메모리)에서 사용됩니다.
• 제자리 정렬: 추가 메모리를 사용하지 않습니다.

단점:

• 비효율적인 비교: O(n^2)의 비교 횟수로 인해 큰 배열에 대해 느릴 수 있습니다.
• 불안정 정렬: 같은 값의 상대적 순서를 유지하지 못합니다.

---

5. Java 구현

import java.util.Arrays;

public class CycleSort {
    public static void cycleSort(int[] arr) {
        int n = arr.length;

        // Traverse the array to place each element at its correct position
        for (int start = 0; start < n - 1; start++) {
            int item = arr[start];
            int pos = start;

            // Count elements smaller than the current item
            for (int i = start + 1; i < n; i++) {
                if (arr[i] < item) {
                    pos++;
                }
            }

            // If the item is already in the correct position, skip
            if (pos == start) {
                continue;
            }

            // Skip duplicates
            while (item == arr[pos]) {
                pos++;
            }

            // Place the item at its correct position
            int temp = arr[pos];
            arr[pos] = item;
            item = temp;

            // Rotate the rest of the cycle
            while (pos != start) {
                pos = start;

                for (int i = start + 1; i < n; i++) {
                    if (arr[i] < item) {
                        pos++;
                    }
                }

                while (item == arr[pos]) {
                    pos++;
                }

                temp = arr[pos];
                arr[pos] = item;
                item = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 1};
        System.out.println("Original Array: " + Arrays.toString(arr));

        cycleSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python 구현

def cycle_sort(arr):
    n = len(arr)

    # Traverse the array to place each element at its correct position
    for start in range(n - 1):
        item = arr[start]
        pos = start

        # Count elements smaller than the current item
        for i in range(start + 1, n):
            if arr[i] < item:
                pos += 1

        # If the item is already in the correct position, skip
        if pos == start:
            continue

        # Skip duplicates
        while item == arr[pos]:
            pos += 1

        # Place the item at its correct position
        arr[pos], item = item, arr[pos]

        # Rotate the rest of the cycle
        while pos != start:
            pos = start

            for i in range(start + 1, n):
                if arr[i] < item:
                    pos += 1

            while item == arr[pos]:
                pos += 1

            arr[pos], item = item, arr[pos]

# Example usage
if __name__ == "__main__":
    arr = [4, 3, 2, 1]
    print("Original Array:", arr)

    cycle_sort(arr)

    print("Sorted Array:", arr)

---

7. 활용 사례

• 쓰기 작업이 제한되거나 비용이 많이 드는 플래시 메모리 또는 EEPROM에서 데이터 이동 횟수를 최소화하는 데 적합합니다.
• 하지만 시간 복잡도가 O(n^2)이므로 대규모 데이터셋에는 적합하지 않습니다.

사이클 정렬은 효율성보다는 독특한 쓰기 최적화 특성 때문에 주로 학습 목적이나 특정 환경에서만 사용됩니다.