팀정렬 알고리즘 활용처 - Java
자바의 Arrays.sort()는 다음과 같은 기준으로 정렬 알고리즘을 선택합니다.
- 원시 타입 배열(
int[],double[]등): Dual-Pivot Quick Sort 사용 - 객체 타입 배열(
Integer[],String[]등): Tim Sort 사용
Dual-Pivot Quick Sort를 선택한 이유
원시 타입 배열을 정렬할 때 사용하는 Dual-Pivot Quick Sort는 기존의 Quick Sort 알고리즘을 개선한 방식입니다
기존 Quick Sort는 하나의 pivot을 사용해 데이터를 분할하지만,
Dual-Pivot Quick Sort는 두 개의 피벗을 사용해 더 빠르게 데이터를 분할하고 정렬할 수 있습니다
왜 객체타입 배열인 경우만 Tim Sort를 사용할까?
원시 타입 배열은 데이터 값 자체가 메모리상에 연속적으로 저장되기 때문에,
참조지역성의 이점을 얻을 수 있습니다
따라서 Dual-Pivot Quick Sort 같은 빠른 정렬 알고리즘을 선택해서 좋은 성능을 발휘합니다
반면, 객체 타입 배열은 값이 아니라 Reference를 저장합니다
배열 자체는 연속된 메모리에 존재하지만,
참조하는 실제 객체들은 힙(Heap) 메모리의 다양한 위치에 흩어져 있습니다
따라서 객체를 접근할 때마다 Cache Hit Rate가 떨어지고,
참조 지역성을 제대로 활용할 수 없습니다
그렇기 때문에 객체 정렬에는 Tim Sort가 더 적합합니다
Tim Sort는 부분적으로 정렬된 데이터를 효과적으로 처리할 수 있고,
최악의 경우에도 O(n log n) 성능을 보장하기 때문입니다
따라서 자바에서는 객체 배열 정렬에 Tim Sort를 사용합니다
Collections.sort()는 어떻게 동작할까?
자바에서 리스트를 정렬할 때 자주 사용하는 Collections.sort()는 내부적으로 Arrays.sort()를 호출합니다
정확히는 리스트를 배열로 변환한 후, Arrays.sort()를 이용해 정렬한 다음
정렬 결과를 다시 리스트로 복사하는 방식입니다
이 과정에서 약간의 오버헤드가 발생할 수 있습니다
따라서 배열을 직접 사용할 수 있는 상황이라면 Arrays.sort()가 더 효율적입니다
참고
