콤 정렬(Comb Sort)

버블 정렬의 일반적인 문제점은 작은 값들이 배열의 끝 부분에 위치할 때 발생한다. 이 문제는 버블 정렬의 속도를 크게 떨어뜨린다. 작은 값(혹은 _거북이_라 불리는)이 거의 전체 배열을 거쳐 이동해야 하기 때문이다. 버블 정렬은 배열의 현재 인덱스와 다음 인덱스를 비교하며, 두 값이 정렬되지 않았을 때 위치를 바꾼다. 결과적으로 값들은 배열 내에서 제자리를 찾아가며 정렬된다.

콤 정렬은 배열 끝 부분에 위치한 거북이 문제를 해결함으로써 버블 정렬을 개선한다. 배열의 현재 인덱스 값과 일정 거리만큼 떨어진 인덱스의 값을 비교한다. 이 방식은 버블 정렬의 최악의 경우를 제거하고, 시간 복잡도를 크게 개선한다.

예제

Comb Sort가 어떻게 동작하는지, 그리고 Bubble Sort와 어떻게 다른지 단계별로 설명한 예제는 여기에서 확인할 수 있다.

Comb Sort의 동작을 시각적으로 확인할 수 있는 이미지도 있다:

알고리즘

버블 정렬과 마찬가지로 배열 내 두 값을 비교한다. 낮은 인덱스의 값이 높은 인덱스의 값보다 크고, 배열 내 순서가 맞지 않을 경우 두 값을 교환한다. 버블 정렬과 다른 점은 비교 대상 값이 일정한 간격(gap)만큼 떨어져 있다는 것이다. 이 간격은 반복을 거치면서 점점 줄어든다.

코드 구현

Comb Sort를 Swift로 구현한 예제는 다음과 같다:

func combSort (input: [Int]) -> [Int] {
    var copy: [Int] = input
    var gap = copy.count
    let shrink = 1.3

    while gap > 1 {
        gap = (Int)(Double(gap) / shrink)
        if gap < 1 {
            gap = 1
        }
    
        var index = 0
        while !(index + gap >= copy.count) {
            if copy[index] > copy[index + gap] {
                swap(&copy[index], &copy[index + gap])
            }
            index += 1
        }
    }
    return copy
}

이 코드는 플레이그라운드에서 테스트할 수 있다. 정렬할 배열을 인자로 넘겨 함수를 호출하면 된다:

combSort(example_array_of_values)

이 함수는 배열의 값을 오름차순으로 정렬한다. 값이 작은 것부터 큰 순서로 정렬된다.

성능

Comb Sort는 Bubble Sort의 최악의 시간 복잡도를 개선하기 위해 만들어졌다. Comb Sort의 최악의 경우 성능은 다항식 시간 복잡도인 O(n^2)를 가진다. 하지만 최상의 경우 Comb Sort는 O(n logn)의 로그 선형 시간 복잡도를 보인다. 이는 Bubble Sort의 성능에 비해 상당한 개선이다.

Bubble Sort와 마찬가지로, Comb Sort의 공간 복잡도는 상수인 O(1)이다. 이는 배열을 제자리에서 정렬하기 때문에 매우 공간 효율적이다.

추가 자료

Comb Sort Wikipedia

Swift Algorithm Club을 위해 Stephen Rutstein이 작성