정렬 알고리즘 (Sorting Algorithms) - Comb 정렬 (Comb Sort)

Comb 정렬 (Comb Sort)

Comb 정렬은 버블 정렬(Bubble Sort)의 개선된 버전으로, 기본적으로 인접한 요소 대신 서로 일정한 간격을 두고 요소를 비교하며 정렬을 진행합니다. 이 간격을 점차 줄여가며 정렬이 이루어집니다. Comb 정렬은 간격 기반의 비교와 삽입 정렬의 요소를 결합하여 성능을 개선한 정렬 방식입니다.

---

1. 주요 특징

1. 간격 (Gap):
   • 배열 요소를 비교할 때 사용하는 간격입니다.
   • 초기값은 배열의 길이로 설정하며, 정렬 진행 중 점차 줄여 나갑니다.
2. Shrinking Factor:
   • 간격을 줄이는 비율입니다. 일반적으로 1.3으로 설정합니다.
   • 이 비율은 알고리즘의 효율성에 영향을 줍니다.
3. 버블 정렬의 개선:
   • 인접한 두 요소만 비교하는 버블 정렬에 비해, Comb 정렬은 처음에 더 멀리 떨어진 요소를 비교하므로 느린 "거북 현상"을 방지합니다.
4. 완전 정렬 단계:
   • 간격이 1로 줄어들면 Comb 정렬은 버블 정렬과 유사하게 작동하며, 배열이 완전히 정렬됩니다.

---

2. 동작 원리

단계 설명:

1. 초기 간격 설정:
   • 초기 간격을 배열 길이로 설정합니다.
   • 간격을 Shrinking Factor로 나눠가며 줄여나갑니다.
2. 비교 및 교환:
   • 현재 간격을 기준으로 배열 요소를 비교하고 필요하면 교환합니다.
3. 간격 감소:
   • 간격이 1에 도달할 때까지 과정을 반복합니다.
4. 최종 확인:
   • 간격이 1인 상태에서 배열이 완전히 정렬될 때까지 진행합니다.

---

3. 시간 복잡도

• 최선 시간 (Best Case): O(n log n)
• 평균 시간 (Average Case): O(n^2 / 2^p) (여기서 p는 간격 감소 횟수)
• 최악 시간 (Worst Case): O(n^2)
• 공간 복잡도: O(1) (제자리 정렬)

---

4. 장점과 단점

장점:

1. 버블 정렬보다 빠름:
   • 초기 비교 범위를 넓게 설정해 정렬 속도를 개선합니다.
2. 간단한 구현:
   • 알고리즘이 비교적 단순하여 구현하기 쉽습니다.
3. 메모리 효율적:
   • 추가 메모리를 사용하지 않는 제자리 정렬(In-Place Sorting)입니다.

단점:

1. 느린 최악의 성능:
   • 최악의 경우 성능이 O(n^2)로 떨어질 수 있습니다.
2. 빠른 정렬 알고리즘과 비교 시 비효율적:
   • 퀵 정렬이나 병합 정렬처럼 O(n log n)의 최악 시간 복잡도를 가진 알고리즘보다 느립니다.

---

5. 예제 코드

Java 구현

import java.util.Arrays;

public class CombSort {

    // Comb Sort Method
    public static void combSort(int[] arr) {
        int n = arr.length;

        // Initialize gap size
        int gap = n;

        // Shrinking factor
        double shrink = 1.3;

        // Flag to check if swapping occurred
        boolean swapped = true;

        while (gap > 1 || swapped) {
            // Update gap for this iteration
            gap = (int) Math.max(1, (gap / shrink));

            swapped = false;

            // Compare and swap elements based on current gap
            for (int i = 0; i + gap < n; i++) {
                if (arr[i] > arr[i + gap]) {
                    // Swap elements
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;

                    swapped = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {34, 2, 10, -9, 56, 43, 3, 22, 15};
        System.out.println("Original Array: " + Arrays.toString(arr));

        combSort(arr);

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

---

Python 구현

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

    # Initialize gap size
    gap = n

    # Shrinking factor
    shrink = 1.3

    # Flag to check if swapping occurred
    swapped = True

    while gap > 1 or swapped:
        # Update gap for this iteration
        gap = max(1, int(gap / shrink))

        swapped = False

        # Compare and swap elements based on current gap
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                # Swap elements
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True

# Example usage
if __name__ == "__main__":
    arr = [34, 2, 10, -9, 56, 43, 3, 22, 15]
    print("Original Array:", arr)

    comb_sort(arr)

    print("Sorted Array:", arr)

---

6. 동작 예시

입력:

• 배열: [34, 2, 10, -9, 56, 43, 3, 22, 15]
• Shrinking Factor: 1.3

동작 과정:

1. 초기 간격 = 9 (배열 길이)
2. 간격 9 → 간격 6 → 간격 4 ...
3. 각 간격에서 비교 및 교환 수행
4. 간격 1에 도달 시 버블 정렬처럼 동작하며 정렬 완료

출력:

• 정렬된 배열: [-9, 2, 3, 10, 15, 22, 34, 43, 56]

---

7. 주요 사용 사례

1. 간단하고 메모리 효율적인 정렬이 필요한 경우.
2. 학습 목적 및 정렬 알고리즘 비교 연구.
3. 데이터 크기가 상대적으로 작을 때 빠르게 정렬해야 하는 상황.

Comb 정렬은 효율성과 간단함이 균형을 이루는 알고리즘으로, 기본 정렬 알고리즘에 대한 학습과 비교에 유용합니다.