[JAVA] Arrays.sort() Collection.sort() 정렬 알고리즘

Java에서 정렬에 대해서 크게 Arrays.sort()와 Collection.sort()가 존재하는데 이 두 메서드는 내부 구현에 차이가 있어 정리를 하고자 한다.

Arrays.sort()

배열을 정리하는데 사용된다. 원시 타입 배열(int[], char[], etc.)와 객체 배열(String[], Integer[], etc.) 모두 정렬할 수 있다.

정렬 방식

원시 타입 배열의 경우, Dual-Pivot Quicksort

 

객체 배열의 경우, TimSort

Collection.sort()

List를 정렬하는데 사용되어 List 인터페이스를 구현한 모든 컬렉션(ArrayList, LinkedList 등)을 정렬할 수 있다.

정렬방식

TimSort 방식으로 정렬을 하는데 TimSort를 정렬에 Arrays.sort()의 메서드를 사용한다.

Arrays.sort는 왜 DualPivotQuickSort를 채택했을까?

1. 성능
   • Quick sort의 경우 pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기에 참조 지역성이 좋으며 메모리를 추가로 사용하지 않는다.
   • 비교 연산 감소 - Dual Pivot Quicksort는 두 개의 피벗을 사용하여 배열을 세 부분으로 나누어 이로인해 평균적으로 비교 연산의 수가 줄어들어 single pivot Quicksort보다 더 빠르게 동작할 수 있습니다.
2. Tim Sort와의 비교
   • 배열에서는 리스트보다 더 빠르게 요소에 접근 할 수 있기 때문에 timsort 보다는 dual pivot quicksort가 더 적합하다.

Tim Sort

이 정렬 알고리즘은 Insertion sort와 Merge Sort를 결합하여 만들어졌으며, 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

동작원리

1. 데이터를 최소 크기의 run(부분적으로 정렬된 데이터의 연속된 구간)으로 분할:
   • 입력 배열을 여러 개의 run으로 나눕니다. MIN_RUN이라는 값이 있으며, 이는 보통 32에서 64 사이입니다.
   • 하지만 run의 크기는 고정되지 않으며, 이미 정렬된 부분을 최대한 활용합니다. 예를 들어, 배열의 일부가 이미 정렬되어 있으면, 그 부분 전체를 하나의 run으로 취급합니다.
2. 각 run을 삽입 정렬(Insertion Sort)로 정렬:
   • 작은 run들은 삽입 정렬을 사용하여 정렬합니다. 삽입 정렬은 작은 배열에서 매우 효율적으로 동작합니다.
3. 정렬된 run들을 병합:
   • 정렬된 run들을 병합하여 더 큰 정렬된 run을 만듭니다. 이 과정은 병합 정렬(Merge Sort)을 사용합니다.
   • 병합 과정에서 galloping mode라는 최적화 기법을 사용하여 두 run이 많이 정렬되어 있을 때 병합을 가속화합니다.
4. 반복적인 병합:
   • 병합된 run들을 다시 병합하여 최종적으로 하나의 정렬된 배열을 만듭니다.
   • 병합 규칙에 따라 stack-like 구조를 사용하여 병합 순서를 관리합니다. 예를 들어, 특정 크기 조건을 만족하지 않으면 병합을 지연시키거나 조정합니다.

Collection.sort는 왜 Tim Sort를 채택했는가?

1. 하이브리드 알고리즘
   • Tim Sort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)의 하이브리드 알고리즘으로 삽입 정렬은 작은 데이터 세트에 대해 매우 빠르게 동작하고 병합 정렬은 큰 데이터 세트에 대해 안정적이고 효융적으로 동작한다.
2. 최악의 경우에 대한 고려
   • Tim Sort는 최악의 경우에도 O(n log n)의 시간 복잡도를 보장하여 정렬 알고리즘에서 매우 중요한 요소로 최악의 경우에도 예측 가능한 성능을 제공한다.
3. 안정 정렬
   • TimSort는 안정 정렬 알고리즘으로 동일한 값의 요소들이 정렬 후에도 원래의 상대적인 순서를 유지한다.

 

결론, 그래서 뭐를 써야하나?

늘 개발하면서 겪는 문제지만 이것은 결국 Trade Off 관계이다. 안전성을 중요시 할 경우, Tim Sort를 속도를 우선시 할 경우, Quick Sort를 사용하면 된다.

 

 

Reference.

https://d2.naver.com/helloworld/0315536

https://www.baeldung.com/cs/quicksort-vs-timsort

https://velog.io/@disdos0928/어떤-정렬-알고리즘을-사용할까