Java에서 Primitive Array 정렬에 Dual-Pivot Quicksort를 선택한 이유

목차

• 원시 배열과 객체 배열의 차이
• Dual-Pivot Quicksort란?
• 원시 배열에서 Dual-Pivot Quicksort를 사용하는 이유
• 정리

---

Java는 원시 배열(primitive array)을 정렬할 때 Arrays.sort() 메서드를 사용하며, 이 메서드는 내부적으로 Dual-Pivot Quicksort를 사용합니다. 반면, 객체 배열(Object array)의 경우 Timsort를 사용합니다.

이 글에서는 원시 배열 정렬에 Dual-Pivot Quicksort가 Timsort보다 선호되는 이유를 원시 배열의 구조와 알고리즘의 특성을 중심으로 설명하겠습니다.

---

원시 배열과 객체 배열의 차이

Java에서 원시 배열과 객체 배열은 메모리 구조와 접근 방식에 차이가 있습니다.

원시 배열

• 데이터가 연속된 메모리 공간에 저장됨
• 비교 연산을 통해 직접 값 비교 가능

객체 배열

• Heap에 메모리가 분산 저장되며, 각 요소가 객체 참조를 가짐
• 객체 간 비교를 위해서는 compareTo() 또는 Comparator가 필요

이러한 차이로 원시 배열과 객체 배열은 서로 다른 정렬 알고리즘이 적합합니다.

---

Dual-Pivot Quicksort란?

Dual-Pivot Quicksort는 전통적인 단일 피벗 퀵소트의 변형으로, 두 개의 피벗을 사용하여 배열을 세 부분으로 분할하는 정렬 알고리즘입니다.

이는 Vladimir Yaroslavskiy에 의해 제안 되었으며, Java 7부터 Arrays.sort()의 기본 알고리즘으로 채택되었습니다.

---

원시 배열에서 Dual-Pivot Quicksort를 사용하는 이유

원시 배열은 연속된 메모리 공간에 데이터를 저장하며, Dual-Pivot Quicksort는 이러한 메모리 구조에서 최적의 성능을 발휘합니다.

메모리 접근 효율성

연속된 메모리 블록에 저장된 데이터는 CPU 캐시 라인에 한 번에 여러 개 로드됩니다. 즉, 하나의 메모리 접근으로 인접한 여러 데이터에 접근할 수 있어 데이터 요청 시 캐시 히트율이 높아집니다.

이로 인해 정렬 과정에서 데이터에 빠르게 접근할 수 있으며, in-place방식의 Dual-Pivot Quicksort의 빈번한 읽기/쓰기 작업 시 전체 성능이 크게 향상됩니다.

비교 연산의 단순성

객체 배열은 객체의 참조를 저장하며, 정렬 시 각 객체의 비교 메서드를 호출해 값을 비교합니다. 이 과정에서 추가적인 오버헤드가 발생합니다.

반면, 원시 배열은 값을 직접 저장합니다. 때문에 정렬 과정에서 단순한 산술 연산으로 빠르게 비교가 가능하며, 불필요한 메서드 호출 오버헤드가 없습니다.

Dual-Pivot 전략과 불안정 정렬

Dual-Pivot Quicksort는 두 개의 피봇으로 배열을 세 부분으로 분할합니다. 이 전략은 평균적인 비교 횟수를 줄일 수 있습니다.

또한 원시 배열은 동일한 값의 상대적 순서가 변경되어도 문제없기 때문에 불안정 정렬을 사용해 불필요한 안정성 유지 작업을 생략할 수 있습니다.

---

정리

• 원시 배열은 연속된 메모리 구조로 캐시 히트율이 높아, in-place 정렬 알고리즘과의 호환성이 뛰어나다.
• 원시 배열은 추가 오버헤드 없이 단순 연산으로 값을 직접 비교할 수 있다.
• 원시 배열은 동일한 값의 상대 순서를 유지할 필요가 없어, 불안정 정렬을 사용해도 무방하다.