퀵 정렬
목표: 배열을 낮은 순서에서 높은 순서로(또는 높은 순서에서 낮은 순서로) 정렬한다.
퀵 정렬은 역사상 가장 유명한 알고리즘 중 하나다. 1959년 토니 호어가 발명했으며, 당시 재귀는 아직 명확하지 않은 개념이었다.
다음은 이해하기 쉬운 Swift 구현 예제다:
func quicksort<T: Comparable>(_ a: [T]) -> [T] {
guard a.count > 1 else { return a }
let pivot = a[a.count/2]
let less = a.filter { $0 < pivot }
let equal = a.filter { $0 == pivot }
let greater = a.filter { $0 > pivot }
return quicksort(less) + equal + quicksort(greater)
}이 코드를 플레이그라운드에 넣고 다음과 같이 테스트할 수 있다:
let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
quicksort(list)퀵 정렬은 어떻게 동작할까? 배열이 주어지면, quicksort()는 "피벗" 변수를 기준으로 배열을 세 부분으로 나눈다. 여기서 피벗은 배열의 중간에 위치한 요소로 선택된다(나중에 피벗을 선택하는 다른 방법도 살펴볼 것이다).
피벗보다 작은 모든 요소는 less라는 새 배열에 들어간다. 피벗과 같은 모든 요소는 equal 배열에 들어간다. 그리고 피벗보다 큰 모든 요소는 greater 배열에 들어간다. 이 때문에 제네릭 타입 T는 Comparable을 준수해야 한다. 그래야 <, ==, > 연산자로 요소를 비교할 수 있다.
이 세 배열을 얻은 후, quicksort()는 less 배열과 greater 배열을 재귀적으로 정렬한다. 그런 다음 정렬된 하위 배열을 equal 배열과 함께 다시 합쳐 최종 결과를 얻는다.
예제를 통해 이해하기
예제를 하나씩 살펴보자. 초기 배열은 다음과 같다:
[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]먼저 피벗 엘리먼트를 선택한다. 여기서는 배열의 중앙에 위치한 8을 선택한다. 이제 배열을 피벗보다 작은 값, 같은 값, 큰 값으로 나눈다:
less: [ 0, 3, 2, 1, 5, -1 ]
equal: [ 8, 8 ]
greater: [ 10, 9, 14, 27, 26 ]이 분할은 꽤 잘 이루어졌다. less와 greater 배열이 대략 비슷한 수의 엘리먼트를 포함하고 있기 때문이다. 따라서 배열을 반으로 나누는 좋은 피벗을 선택한 셈이다.
less와 greater 배열은 아직 정렬되지 않았으므로, quicksort()를 다시 호출해 이 두 하위 배열을 정렬한다. 이 과정은 동일하게 진행된다. 피벗을 선택하고 배열을 세 개의 더 작은 부분으로 나눈다.
less 배열을 살펴보자:
[ 0, 3, 2, 1, 5, -1 ]이번에는 중앙에 위치한 1을 피벗으로 선택한다. (2를 선택해도 상관없다.) 다시 피벗을 기준으로 세 개의 하위 배열을 만든다:
less: [ 0, -1 ]
equal: [ 1 ]
greater: [ 3, 2, 5 ]아직 작업이 끝나지 않았으므로, quicksort()를 재귀적으로 호출해 less와 greater 배열을 정렬한다. less 배열을 다시 보자:
[ 0, -1 ]이번에는 -1을 피벗으로 선택한다. 이제 하위 배열은 다음과 같다:
less: [ ]
equal: [ -1 ]
greater: [ 0 ]less 배열은 비어 있다. -1보다 작은 값이 없기 때문이다. 다른 배열은 각각 하나의 엘리먼트만 포함하고 있다. 이 시점에서 재귀의 현재 단계는 완료되었고, 이전 greater 배열을 정렬하기 위해 돌아간다.
이전 greater 배열은 다음과 같았다:
[ 3, 2, 5 ]이전과 동일한 방식으로 진행된다. 중앙에 위치한 2를 피벗으로 선택하고 하위 배열을 채운다:
less: [ ]
equal: [ 2 ]
greater: [ 3, 5 ]여기서는 3을 피벗으로 선택하는 것이 더 나았을 것이다. 그랬다면 더 빨리 작업을 마칠 수 있었을 것이다. 하지만 이제는 greater 배열을 다시 재귀적으로 정렬해야 한다. 따라서 좋은 피벗을 선택하는 것이 중요하다. 너무 많은 '나쁜' 피벗을 선택하면 퀵소트가 실제로 매우 느려진다. 이에 대해서는 뒤에서 더 자세히 설명한다.
greater 하위 배열을 분할하면 다음과 같다:
less: [ 3 ]
equal: [ 5 ]
greater: [ ]이제 이 재귀 단계에서 작업이 완료된다. 더 이상 배열을 나눌 수 없기 때문이다.
이 과정은 모든 하위 배열이 정렬될 때까지 반복된다. 그림으로 보면 다음과 같다:
이제 색상으로 표시된 박스를 왼쪽에서 오른쪽으로 읽으면 정렬된 배열을 얻을 수 있다:
[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]이 결과는 8이 초기 피벗으로서 좋은 선택이었음을 보여준다. 정렬된 배열에서도 8이 중앙에 위치하기 때문이다.
이 예제를 통해 퀵소트의 기본 원리를 이해할 수 있기를 바란다. 하지만 이 버전의 퀵소트는 그다지 빠르지 않다. 동일한 배열을 세 번 filter()하기 때문이다. 배열을 분할하는 더 효율적인 방법도 존재한다.
파티셔닝
배열을 피벗을 기준으로 나누는 과정을 파티셔닝이라고 한다. 이때 사용할 수 있는 여러 가지 파티셔닝 기법이 존재한다.
예를 들어, 다음과 같은 배열이 있다고 가정하자:
[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
이 배열에서 중앙에 위치한 요소 8을 피벗으로 선택하면, 파티셔닝 후 배열은 다음과 같이 변한다:
[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]
----------------- -----------------
피벗보다 작은 요소들 피벗보다 큰 요소들
여기서 중요한 점은 파티셔닝 후 피벗 요소는 이미 최종 정렬된 위치에 있다는 것이다. 나머지 숫자들은 아직 정렬되지 않았으며, 단순히 피벗 값을 기준으로 분할된 상태다. 퀵 정렬은 모든 값이 최종 위치에 오기까지 배열을 여러 번 파티셔닝한다.
파티셔닝 과정에서 요소들의 상대적 순서가 유지된다는 보장은 없다. 따라서 피벗 8을 기준으로 파티셔닝한 후 다음과 같은 결과가 나올 수도 있다:
[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]
이때 보장되는 것은 피벗 왼쪽에는 더 작은 요소들이, 오른쪽에는 더 큰 요소들이 위치한다는 점이다. 파티셔닝이 동일한 요소들의 원래 순서를 바꿀 수 있기 때문에, 퀵 정렬은 병합 정렬과 달리 "안정적인" 정렬을 제공하지 않는다. 하지만 대부분의 경우 이는 큰 문제가 되지 않는다.
로무토 분할 기법
이전에 보여준 퀵소트 예제에서는 Swift의 filter() 함수를 세 번 호출해 분할을 수행했다. 이 방법은 그다지 효율적이지 않다. 이제 원본 배열을 직접 수정하는 제자리(in place) 방식으로 동작하는 더 효율적인 분할 알고리즘을 살펴보자.
다음은 Swift로 구현한 로무토 분할 기법이다:
func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[high]
var i = low
for j in low..<high {
if a[j] <= pivot {
a.swapAt(i, j)
i += 1
}
}
a.swapAt(i, high)
return i
}이 코드를 플레이그라운드에서 테스트하려면 다음과 같이 작성한다:
var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
let p = partitionLomuto(&list, low: 0, high: list.count - 1)
list // 결과 확인list는 var로 선언해야 한다. partitionLomuto() 함수가 배열의 내용을 직접 변경하기 때문이다(이 함수는 inout 매개변수로 배열을 받는다). 이 방식은 새로운 배열 객체를 할당하는 것보다 훨씬 효율적이다.
low와 high 매개변수는 퀵소트 내부에서 사용할 때 필요하다. 항상 전체 배열을 다시 분할할 필요는 없고, 점점 작아지는 특정 범위만 분할하면 되기 때문이다.
이전에는 배열의 중간 요소를 피벗으로 사용했지만, 로무토 알고리즘은 항상 마지막 요소인 a[high]를 피벗으로 사용한다. 이 예제에서는 8이 항상 피벗이 되도록 8과 26의 위치를 바꿔 8이 배열의 끝에 위치하도록 했다.
분할 후 배열은 다음과 같이 된다:
[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]
*
변수 p는 partitionLomuto() 호출의 반환값을 가지며, 이 값은 7이다. 이는 새로운 배열에서 피벗 요소의 인덱스다(별표로 표시).
왼쪽 파티션은 0부터 p-1까지이며 [ 0, 3, 2, 1, 5, 8, -1 ]이다. 오른쪽 파티션은 p+1부터 끝까지이며 [ 9, 10, 14, 26, 27 ]이다(오른쪽 파티션이 이미 정렬된 것은 우연이다).
흥미로운 점은 배열에 8이 여러 번 등장한다는 것이다. 그중 하나는 중간에 위치하지 않고 왼쪽 파티션에 들어갔다. 이는 로무토 알고리즘의 작은 단점으로, 중복 요소가 많을 경우 퀵소트의 속도를 느리게 만든다.
로무토 알고리즘은 어떻게 동작할까? 핵심은 for 루프에 있다. 이 루프는 배열을 네 개의 영역으로 나눈다:
a[low...i]는 피벗보다 작거나 같은 모든 값을 포함한다.a[i+1...j-1]는 피벗보다 큰 모든 값을 포함한다.a[j...high-1]은 아직 확인하지 않은 값들이다.a[high]는 피벗 값이다.
ASCII 아트로 표현하면 배열은 다음과 같이 나뉜다:
[ 피벗보다 작거나 같은 값 | 피벗보다 큰 값 | 아직 확인하지 않은 값 | 피벗 ]
low i i+1 j-1 j high-1 high
루프는 low부터 high-1까지 각 요소를 차례로 확인한다. 현재 요소의 값이 피벗보다 작거나 같으면 스왑을 통해 첫 번째 영역으로 이동시킨다.
참고: Swift에서
(x, y) = (y, x)는x와y의 값을 스왑하는 편리한 방법이다.swap(&x, &y)로도 작성할 수 있다.
루프가 끝나면 피벗은 여전히 배열의 마지막 요소다. 따라서 피벗보다 큰 첫 번째 요소와 스왑한다. 이제 피벗은 <= 영역과 > 영역 사이에 위치하며 배열이 올바르게 분할된다.
예제를 단계별로 살펴보자. 시작 배열은 다음과 같다:
[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j
초기에는 "아직 확인하지 않은" 영역이 인덱스 0부터 11까지다. 피벗은 인덱스 12에 있다. "피벗보다 작거나 같은 값"과 "피벗보다 큰 값" 영역은 비어 있다. 아직 어떤 값도 확인하지 않았기 때문이다.
첫 번째 값인 10을 확인한다. 이 값은 피벗보다 작은가? 아니므로 다음 요소로 넘어간다.
[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j
이제 "아직 확인하지 않은" 영역은 인덱스 1부터 11까지다. "피벗보다 큰 값" 영역에는 10이 포함되며, "피벗보다 작거나 같은 값" 영역은 여전히 비어 있다.
두 번째 값인 0을 확인한다. 이 값은 피벗보다 작은가? 맞다. 따라서 10과 0을 스왑하고 i를 한 칸 앞으로 이동시킨다.
[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j
이제 "아직 확인하지 않은" 영역은 인덱스 2부터 11까지다. "피벗보다 큰 값" 영역에는 여전히 10이 포함되며, "피벗보다 작거나 같은 값" 영역에는 0이 포함된다.
세 번째 값인 3을 확인한다. 이 값은 피벗보다 작으므로 10과 스왑한다.
[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j
"피벗보다 작거나 같은 값" 영역은 이제 [ 0, 3 ]이다. 한 번 더 진행해 보자. 9는 피벗보다 크므로 그냥 넘어간다.
[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j
이제 "피벗보다 큰 값" 영역에는 [ 10, 9 ]가 포함된다. 이 방식으로 계속 진행하면 최종적으로 다음과 같은 결과를 얻는다:
[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
low high
i j
마지막으로 a[i]와 a[high]를 스왑해 피벗을 제자리에 놓는다:
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]
low high
i j
그리고 i, 즉 피벗 요소의 인덱스를 반환한다.
참고: 알고리즘이 어떻게 동작하는지 아직 명확하지 않다면, 플레이그라운드에서 직접 실습해 보며 루프가 어떻게 이 네 영역을 만드는지 확인해 보자.
이 분할 기법을 사용해 퀵소트를 구현해 보자. 코드는 다음과 같다:
func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionLomuto(&a, low: low, high: high)
quicksortLomuto(&a, low: low, high: p - 1)
quicksortLomuto(&a, low: p + 1, high: high)
}
}이제 훨씬 간단해졌다. 먼저 partitionLomuto()를 호출해 배열을 피벗(항상 배열의 마지막 요소)을 기준으로 재배열한다. 그런 다음 quicksortLomuto()를 재귀적으로 호출해 왼쪽과 오른쪽 파티션을 정렬한다.
실행해 보자:
var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quicksortLomuto(&list, low: 0, high: list.count - 1)로무토 기법은 유일한 분할 기법은 아니지만, 이해하기 가장 쉽다. 호어 기법보다는 효율성이 떨어지며, 스왑 연산이 더 많이 필요하다.
호어의 분할 방식
이 분할 방식은 퀵소트의 발명가인 호어가 고안한 것이다.
다음은 코드다:
func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[low]
var i = low - 1
var j = high + 1
while true {
repeat { j -= 1 } while a[j] > pivot
repeat { i += 1 } while a[i] < pivot
if i < j {
a.swapAt(i, j)
} else {
return j
}
}
}이 코드를 플레이그라운드에서 테스트하려면 다음과 같이 실행한다:
var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]
let p = partitionHoare(&list, low: 0, high: list.count - 1)
list // 결과 확인호어의 방식에서는 피벗이 항상 배열의 첫 번째 요소인 a[low]가 된다. 여기서도 피벗 요소로 8을 사용한다.
결과는 다음과 같다:
[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]
이번에는 피벗이 중간에 위치하지 않는다. 로무토 방식과 달리 반환 값이 새로운 배열에서 피벗 요소의 인덱스가 되지 않는다.
대신, 배열은 [low...p]와 [p+1...high] 두 영역으로 분할된다. 여기서 반환 값 p는 6이므로, 두 파티션은 [ -1, 0, 3, 8, 2, 5, 1 ]과 [ 27, 10, 14, 9, 8, 26 ]가 된다.
피벗은 두 파티션 중 하나의 내부 어딘가에 위치하지만, 알고리즘은 어느 쪽인지 또는 정확한 위치를 알려주지 않는다. 피벗 값이 여러 번 나타나면, 일부 인스턴스는 왼쪽 파티션에, 다른 인스턴스는 오른쪽 파티션에 위치할 수 있다.
이러한 차이로 인해 호어의 퀵소트 구현은 약간 다르다:
func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionHoare(&a, low: low, high: high)
quicksortHoare(&a, low: low, high: p)
quicksortHoare(&a, low: p + 1, high: high)
}
}호어의 분할 방식이 정확히 어떻게 동작하는지는 독자들이 직접 알아보는 과제로 남겨두겠다. :-)
적절한 피벗 선택하기
Lomuto의 파티셔닝 방식은 항상 배열의 마지막 요소를 피벗으로 선택한다. Hoare의 방식은 첫 번째 요소를 사용한다. 하지만 이 피벗들이 항상 좋은 선택이라고 보장할 수 없다.
피벗으로 나쁜 값을 선택하면 어떤 일이 벌어지는지 살펴보자. 배열이 다음과 같다고 가정하자.
[ 7, 6, 5, 4, 3, 2, 1 ]
Lomuto 방식을 사용하고, 피벗은 마지막 요소인 1이다. 피벗을 기준으로 분할하면 다음과 같은 배열이 만들어진다.
피벗보다 작은 값: [ ]
피벗과 같은 값: [ 1 ]
피벗보다 큰 값: [ 7, 6, 5, 4, 3, 2 ]
이제 "피벗보다 큰" 부분 배열을 재귀적으로 분할하면 다음과 같다.
피벗보다 작은 값: [ ]
피벗과 같은 값: [ 2 ]
피벗보다 큰 값: [ 7, 6, 5, 4, 3 ]
다시 한 번 분할하면:
피벗보다 작은 값: [ ]
피벗과 같은 값: [ 3 ]
피벗보다 큰 값: [ 7, 6, 5, 4 ]
이 과정이 계속 반복된다.
이는 좋지 않은 상황이다. 퀵소트가 훨씬 느린 삽입 정렬로 퇴보하게 된다. 퀵소트가 효율적으로 동작하려면 배열을 대략 두 부분으로 나누어야 한다.
이 예제에서 최적의 피벗은 4였다. 그렇다면 다음과 같은 결과를 얻는다.
피벗보다 작은 값: [ 3, 2, 1 ]
피벗과 같은 값: [ 4 ]
피벗보다 큰 값: [ 7, 6, 5 ]
이런 이유로 항상 첫 번째나 마지막 요소 대신 중간 요소를 선택해야 한다고 생각할 수 있다. 하지만 다음과 같은 상황을 상상해 보자.
[ 7, 6, 5, 1, 4, 3, 2 ]
이 경우 중간 요소는 1이고, 이전 예제와 같은 나쁜 결과를 초래한다.
이상적으로, 피벗은 파티셔닝하는 배열의 중간값이어야 한다. 즉, 정렬된 배열의 중앙에 위치한 요소다. 물론 배열을 정렬하기 전에는 중간값을 알 수 없으니, 이는 닭과 달걀의 문제와 같다. 하지만 좋은 피벗을 선택하는 몇 가지 방법이 있다.
한 가지 방법은 "세 값의 중간값"을 사용하는 것이다. 이 방법은 부분 배열의 첫 번째, 중간, 마지막 요소 중 중간값을 찾는다. 이론적으로 이는 실제 중간값에 대한 좋은 근사치를 제공한다.
또 다른 일반적인 해결책은 피벗을 무작위로 선택하는 것이다. 때로는 최적이 아닌 피벗을 선택할 수도 있지만, 평균적으로 매우 좋은 결과를 얻는다.
무작위로 선택한 피벗을 사용해 퀵소트를 구현하는 방법은 다음과 같다.
func quicksortRandom<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high) // 1
(a[pivotIndex], a[high]) = (a[high], a[pivotIndex]) // 2
let p = partitionLomuto(&a, low: low, high: high)
quicksortRandom(&a, low: low, high: p - 1)
quicksortRandom(&a, low: p + 1, high: high)
}
}이전과 두 가지 중요한 차이점이 있다:
-
random(min:max:)함수는min...max범위 내의 정수를 반환한다. 이 값이 피벗 인덱스다. -
Lomuto 방식은
a[high]가 피벗 요소가 되길 기대하므로,partitionLomuto()를 호출하기 전에a[pivotIndex]와a[high]를 교환해 피벗 요소를 끝으로 이동시킨다.
정렬 함수에서 무작위 숫자를 사용하는 것이 이상하게 보일 수 있지만, 퀵소트가 모든 상황에서 효율적으로 동작하도록 하려면 필요하다. 나쁜 피벗을 선택하면 퀵소트의 성능이 **O(n^2)**로 매우 나빠질 수 있다. 하지만 무작위 숫자 생성기를 사용해 평균적으로 좋은 피벗을 선택하면, 기대 실행 시간이 **O(n log n)**이 되어 정렬 알고리즘의 최고 성능을 달성할 수 있다.
네덜란드 국기 분할
하지만 더 개선할 부분이 있다! 앞서 퀵소트의 첫 번째 예제에서 배열이 다음과 같이 분할된 것을 보았다:
[ 피벗보다 작은 값 | 피벗과 같은 값 | 피벗보다 큰 값 ]
하지만 Lomuto 분할 방식에서는 피벗이 여러 번 나타날 경우 중복된 값이 왼쪽 절반에 위치한다. Hoare 방식에서는 피벗이 배열 전체에 흩어질 수 있다. 이 문제를 해결하기 위한 방법이 바로 "네덜란드 국기" 분할이다. 이 이름은 네덜란드 국기가 세 개의 색띠로 이루어져 있는 것처럼, 우리가 원하는 세 개의 분할 영역과 유사하기 때문에 붙여졌다.
이 방식의 코드는 다음과 같다:
func partitionDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {
let pivot = a[pivotIndex]
var smaller = low
var equal = low
var larger = high
while equal <= larger {
if a[equal] < pivot {
swap(&a, smaller, equal)
smaller += 1
equal += 1
} else if a[equal] == pivot {
equal += 1
} else {
swap(&a, equal, larger)
larger -= 1
}
}
return (smaller, larger)
}이 코드는 Lomuto 방식과 매우 유사하게 동작하지만, 루프가 배열을 네 개의 (비어 있을 수도 있는) 영역으로 분할한다:
[low ... smaller-1]은 피벗보다 작은 모든 값을 포함한다.[smaller ... equal-1]은 피벗과 같은 모든 값을 포함한다.[equal ... larger]은 피벗보다 큰 모든 값을 포함한다.[larger ... high]는 아직 확인하지 않은 값들이다.
이 방식은 피벗이 a[high]에 위치한다고 가정하지 않는다. 대신, 피벗으로 사용할 엘리먼트의 인덱스를 직접 전달해야 한다.
사용 예제:
var list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
partitionDutchFlag(&list, low: 0, high: list.count - 1, pivotIndex: 10)
list // 결과 확인이번에는 다른 8의 인덱스를 전달했다. 결과는 다음과 같다:
[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]
두 개의 8이 중간에 위치한 것을 확인할 수 있다. partitionDutchFlag()의 반환 값은 튜플 (6, 7)이다. 이는 피벗 값(들)이 포함된 범위를 나타낸다.
이 방식을 퀵소트에서 사용하는 방법은 다음과 같다:
func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high)
let (p, q) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: pivotIndex)
quicksortDutchFlag(&a, low: low, high: p - 1)
quicksortDutchFlag(&a, low: q + 1, high: high)
}
}네덜란드 국기 분할을 사용하면 배열에 중복된 엘리먼트가 많을 때 퀵소트의 효율성을 높일 수 있다. (이 말은 단순히 내가 네덜란드인이어서 하는 말이 아니다!)
참고: 위의
partitionDutchFlag()구현은 두 배열 엘리먼트의 내용을 교환하기 위해 커스텀swap()루틴을 사용한다. Swift의 기본swap()과 달리, 이 루틴은 두 인덱스가 동일한 배열 엘리먼트를 참조할 때 오류를 발생시키지 않는다. 코드는 Quicksort.swift에서 확인할 수 있다.
관련 자료
Swift Algorithm Club을 위해 Matthijs Hollemans가 작성