Dual-Pivot Quick Sort 알고리즘 동작과정

Dual-Pivot Quick Sort 알고리즘은 두개의 피벗을 사용해 배열을 세부분으로 나누어 정렬하는 알고리즘입니다
실제 데이터 예시를 통해 정렬 알고리즘의 동작과정을 살펴보겠습니다

다음과 같은 숫자 배열을 오름차순으로 정렬하겠습니다
[8, 4, 7, 3, 9, 2, 6, 5, 1]

1회차 동작과정

두 피벗을 선택합니다
일반적으로 양 끝이 선택되므로 8과 1을 선택하겠습니다

• L: 왼쪽 피벗 (8)
• R: 오른쪽 피벗 (1)

먼저 두 피벗은 다음과 같은 조건을 만족해야합니다
L < R

현재 L피벗이 피벗의 값보다 크므로 두 피벗을 교환합니다
[1, 4, 7, 3, 9, 2, 6, 5, 8]

이제 다음 조건을 만족시켜야합니다

• x: 피벗을 제외한 특정 원소
• x < L: 왼쪽 파티션 배치
• L < x < R: 중간 파티션 배치
• R < x : 오른쪽 파티션 배치
  결과적으로 다음과 같은 배열이 완성됩니다
  [1, 4, 7, 3, 2, 6, 5, 8, 9]

2회차 동작 과정

2회차 부터는 재귀적으로 앞선 동작과정을 반복합니다
L과 R은 원본 피봇 배열 인덱스에서 증감하여 다음과 같이 설정됩니다

• L: 4
• R: 5

이번 피벗은 L<R조건을 만족시킵니다
따라서 교환없이 파티션 배치 조건을 만족시키도록 배치합니다

결과적으로 다음과 같은 배열이 완성됩니다
[1, [3, 2], 4, 5, [7, 6], 8, 9]

3회차 동작과정

다시 재귀적으로 왼쪽 파티션부터 정렬하겠습니다
이어서 다음과 같이 피벗이 설정됩니다

• L: 3
• R: 2

L<R 조건을 만족시키기 위해 두 피벗의 값을 변경합니다
교환 후, 범위 내 원소가 더 없으므로 추가 분할없이 종료됩니다
[1, 2, 3, 4, 5, [7, 6], 8, 9]

4회차 동작 과정

이번에는 재귀적으로 오른쪽 파티션을 정렬하겠습니다
다음과 같이 피벗이 설정됩니다

• L: 7
• R: 6

L<R 조건을 만족시키기 위해 두 피벗의 값을 변경합니다
범위 내 원소가 더 없으므로 추가 분할 없이 종료됩니다
[1, 2, 3, 4, 5, 6, 7, 8, 9]

최종적으로 오름차순 정렬된 배열이 완성되었습니다
[1, 2, 3, 4, 5, 6, 7, 8, 9]

정리

Dual-Pivot Quick Sort 알고리즘은 두 피벗을 기준으로 세개의 파티션으로 분할해 정렬하는 알고리즘입니다
최선과 평균적인 상황에서 시간복잡도는 O(nlogn)으로 기존 Quick Sort보다 더 빠른 성능을 보입니다

실제로 자바에서는 참조 지역성의 이점을 얻을 수 있는 원시타입의 배열에서
Dual-Pivot Quick Sort 알고리즘을 사용하고 있습니다