인트로소트(IntroSort)

목표: 배열을 낮은 순서에서 높은 순서로(또는 높은 순서에서 낮은 순서로) 정렬한다.

인트로소트는 Swift가 컬렉션을 정렬할 때 사용하는 알고리즘이다. 인트로소트는 1993년 David Musser가 C++ 표준 라이브러리를 위한 범용 정렬 알고리즘으로 고안한 하이브리드 알고리즘이다.

인트로소트의 전통적인 구현은 재귀적 퀵소트를 사용하며, 재귀 깊이가 특정 최대값에 도달하면 힙소트로 전환한다. 이 최대값은 컬렉션의 요소 수에 따라 결정되며, 일반적으로 2 * log(n)이다. 이 '전환'이 필요한 이유는 퀵소트가 특정 분기에서 2 * log(n)번의 재귀 후에도 해결책을 찾지 못했다면, 최악의 경우에 직면해 복잡도가 O(n^2)로 악화되었을 가능성이 높기 때문이다. 이 알고리즘을 더욱 최적화하기 위해 Swift 구현에서는 각 재귀 단계에서 추가적인 단계를 도입한다. 이 단계에서는 파티션의 요소 수가 20개 미만일 경우 삽입 정렬을 사용해 파티션을 정렬한다.

숫자 20은 삽입 정렬이 이 크기의 리스트에서 보이는 성능을 관찰해 얻은 경험적 값이다.

다음은 의사코드로 구현한 예제이다:

procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introSort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 20:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // 피벗은 median of 3 방식으로 선택
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

예제 살펴보기

예제를 통해 자세히 알아보자. 초기 배열은 다음과 같다.

[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

이 예제에서 maxDepth는 2이고, 삽입 정렬이 시작되는 파티션 크기는 5라고 가정한다.

인트로 정렬의 첫 번째 반복은 삽입 정렬을 시도하는 것으로 시작한다. 컬렉션의 요소가 13개이므로 대신 힙 정렬을 시도한다. 힙 정렬이 실행되기 위한 조건은 maxdepth == 0이 참일 때이다. 첫 번째 반복에서 maxdepth는 2이므로 인트로 정렬은 기본적으로 퀵 정렬을 사용한다.

partition 메서드는 첫 번째 요소, 중간 요소, 마지막 요소를 선택하고 이를 정렬한 후 새로운 중간 값을 피벗으로 사용한다.

[ 10, 8, 26 ] -> [ 8, 10, 26 ]

이제 배열은 다음과 같다.

[ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]

10이 피벗이다. 피벗을 선택한 후, partition 메서드는 피벗보다 작은 모든 요소를 왼쪽으로, 피벗보다 크거나 같은 모든 요소를 오른쪽으로 이동시키기 위해 요소를 교환한다.

[ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10, 27, 14, 26 ]

교환으로 인해 피벗의 인덱스가 변경되고 반환된다. 인트로 정렬의 다음 단계는 두 하위 배열에 대해 재귀적으로 자신을 호출하는 것이다.

less: [ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]
greater: [ 27, 14, 26 ]

maxDepth: 1, branch: less

[ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]

배열의 크기가 여전히 5보다 크기 때문에 삽입 정렬이 시작될 조건을 충족하지 않는다. 이번 반복에서 maxDepth가 1 감소했지만 여전히 0보다 크므로 힙 정렬은 동작하지 않는다.

이전 반복과 마찬가지로 퀵 정렬이 선택되고, `partition` 메서드가 피벗을 선택한다. 피벗보다 작은 요소는 왼쪽으로, 피벗보다 크거나 같은 요소는 오른쪽으로 정렬된다.

array: [ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]
pivot candidates: [ 8, 1, 10] -> [ 1, 8, 10]
pivot: 8
before partition: [ 1, 0, 3, 9, 2, 8, 5, 8, -1, 10 ]
after partition: [ 1, 0, 3, -1, 2, 5, 8, 8, 9, 10 ]

less: [ 1, 0, 3, -1, 2, 5, 8 ]
greater: [ 8, 9, 10 ]

[ 1, 0, 3, -1, 2, 5, 8 ]

이전과 마찬가지로, less와 greater에 대해 재귀적으로 인트로소트를 실행한다. 이번에는 less의 개수가 5를 초과하므로 삽입 정렬을 사용하지 않는다. 하지만 maxDepth가 다시 1 감소하여 0이 되었고, 이제 힙 정렬이 배열을 정렬한다.

heapsort -> [ -1, 0, 1, 2, 3, 5, 8 ]

maxDepth: 0, branch: greater

[8, 9, 10]

이 재귀에서 greater 브랜치의 요소 개수는 3개로, 5개보다 작기 때문에 이 파티션은 insertionSort를 사용해 정렬한다.

insertionSort -> [8, 9, 10]

maxDepth = 1로 돌아가서, greater 분기 처리

[ 27, 14, 26 ]

이 시점에서 원본 배열은 다음과 같이 변경되었다.

[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 27, 14, 26 ]

이제 less 파티션은 정렬되었고, greater 파티션의 개수가 3이므로 삽입 정렬을 통해 [ 14, 26, 27 ]을 정렬한다.

배열이 최종적으로 정렬되었다.

[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]

인트로소트(IntroSort)

예제 살펴보기

maxDepth: 0, branch: greater

maxDepth = 1로 돌아가서, greater 분기 처리

관련 자료