@Test
public void arrayTest() {
int[] array = new int[]{1, 3 , 5, 4, 2};
Arrays.sort(array);
System.out.println("array = " + Arrays.toString(array));
}
@Test
public void collectionTest() {
List<Integer> collection = new ArrayList<>(List.of(1, 3, 5, 4, 2));
Collections.sort(collection);
System.out.println("collection = " + collection);
}Java를 사용하다보면 위와 같이 정렬을 사용하는 경우가 자주 나타난다.
Arrays.sort와 Collections.sort는 둘다 정렬하는 메소드이지만 내부 정렬 알고리즘은 다르게 사용된다.
Arrays.sort()
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}먼저 Arrays.sort를 살펴보면 위 코드에서 확인할 수 있듯이 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)를 사용한다.
듀얼피봇 퀵정렬은 일반적인 퀵정렬과는 다르게 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬을 진행한다고 한다. 이 정렬방식은 랜덤 데이터에 대해서 평균적으로 퀵소트 보다 좋은 성능을 낸다고 알려져있다.
Collections.sort()
/**
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
* TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
*
* @param a the array to be sorted
* @throws ClassCastException if the array contains elements that are not
* <i>mutually comparable</i> (for example, strings and integers)
* @throws IllegalArgumentException (optional) if the natural
* ordering of the array elements is found to violate the
* {@link Comparable} contract
*/
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}Collections.sort는 Arrays.sort와 달리 Tim 정렬을 사용한다. Tim 정렬은 삽입(Insertion) 정렬과 합병(Merge) 정렬을 결합하여 만든 정렬이다. 그리고 Java 7부터 Tim 정렬을 채택하여 사용하고 있다고 한다.
Arrays.sort() VS Collections.sort()
Arrays를 정렬했을때와 Collections를 정렬했을때 왜 사용하는 알고리즘이 다를까? 그 이유는 참조 지역성 원리(Local of Reference)에 있다.
참조 지역성의 원리란 동일한 값 또는 해당 값의 근처에 있는 스토리지 위치가 자주 액세스되는 특성을 말한다. 이 참조 지역성의 원리는 CPU의 캐싱 전략에 영항을 미친다. 즉, CPU가 데이터를 엑세스하며 해당 데이터만이 아니라 인접한 메모리에 있는 데이터 또한 캐시 메모리에 함께 올려둔다.
정렬의 실제 동작 시간은 C * 시간복잡도 + a라고 한다. a는 상대적으로 무시할 수 있는 값이지만 시간복잡도에 곱해지는 C의 영향도는 고려를 해야한다. 이 C라는 값이 바로 참조 지역성 원리가 영향을 미친다.
Array는 메모리적으로 각 값들이 연속적인 주소를 가지고 있기 때문에 C의 값이 낮다. 그래서 참조 지역성이 좋은 퀵 정렬을 이용하면 충분한 성능을 제공할 수 있다고 한다. 하지만 Collection은 List를 기준으로 봤을때 메모리간 인접한 ArrayList 뿐만 아니라 메모리적으로 산발적인 LinkedList도 함께 존재한다. 따라서 참조 인접성이 좋지 않고 C의 값이 상대적으로 높다고 한다. 이럴 때는 퀵 정렬 보다는 합병정렬과 삽입정렬을 병합한 Tim 정렬을 이용하는게 평균적으로 더 좋은 성능을 기대할 수 있다고 한다.
[참조]
