Dual-Pivot Quick Sort 알고리즘이란?

Dual-Pivot Quick Sort는 기존 퀵 정렬의 변형된 형태로, 하나의 피벗을 사용하는 기존 퀵 정렬과 달리
두 개의 피벗을 사용하여 데이터를 세 영역으로 나누어서 정렬하는 알고리즘입니다

기본원리

Dual-Pivot Quick 정렬 알고리즘은 다음과 같은 원리로 동작합니다.

1. 두 개의 피벗 선택

• 배열에서 첫 번째 원소와 마지막 원소를 피벗으로 선택합니다
• 두 피벗이 반드시 왼쪽 피벗 <= 오른쪽 피벗을 만족하도록 합니다

2. 배열을 세 영역으로 분할

두 피벗을 기준으로 배열의 데이터를 다음과 같이 분할합니다:

• 첫 번째 영역: 왼쪽 피벗보다 작은 값들
• 두 번째 영역: 왼쪽 피벗과 오른쪽 피벗 사이의 값들
• 세 번째 영역: 오른쪽 피벗보다 큰 값들

3. 재귀적 정렬 수행

• 각 영역에 대해 다시 Dual-Pivot Quick Sort를 재귀적으로 적용합니다
• 모든 영역이 정렬될 때까지 이 과정을 반복합니다

시간복잡도

최선과 평균적인 상황에서 시간복잡도는 O(nlogn)이며, 기존 Quick Sort보다 더 빠른 속도를 보입니다
다만, 최악의 경우 배열이 불균형하게 분할되며 O(n^2)의 성능이 발생할 수 있습니다

공간복잡도

Dual-Pivot Quick Sort는 추가적인 배열 사용이 없는 in-place 정렬 알고리즘입니다

• 일반적으로 사용하는 메모리는 재귀 호출로 인한 스택입니다
• 평균적인 공간복잡도는 O(logn)이며, 최악의 경우에도 O(n)의 공간복잡도를 넘지 않습니다

장점

• 기존 Quick Sort보다 더 빠른 성능을 가집니다
• 두 개의 피벗을 사용하여 데이터 분할이 더욱 균형적으로 이루어질 수 있습니다
• 추가적인 배열 공간을 거의 사용하지 않아 참조 지역성이 좋습니다

단점

• 정렬 후 같은 값들의 상대적 순서가 보장되지 않는 불안정 정렬입니다
• 두 피벗을 잘못 선택할 경우 최악의 경우O(n^2)의 성능이 발생할 수 있습니다

결론

Dual-Pivot Quick Sort는 Quick Sort 알고리즘을 두 개의 피벗으로 개선하여, 효율을 높인 알고리즘입니다
평균적으로 O(nlogn)의 시간복잡도를 가지며,
Java의 기본 배열 정렬 알고리즘으로 채택될만큼 입증된 성능을 보여줍니다

그러나 불안정 정렬, 최악의 경우 O(n^2)의 시간복잡도를 가진다는 단점도 가지고 있습니다