[Java] Java의 정렬 알고리즘 - Arrays와 Collections

안녕하세요. 오늘 포스팅은 Java의 Collection에서 사용하고 있는 정렬에 대해서 알아보려고 합니다. Java를 사용하다보면 정렬해서 처리해야할 경우가 생깁니다. 그럴경우 아래와 같이코드를 작성하곤 합니다. 아래 코드를 볼때 결과값이 1, 2, 3, 4, 5로 정렬되게 나온다는 것을 예측할 수 있을것입니다.

@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의 정렬, 내부에는 어떻게 구현되어 있을까요? 오늘은 Java의 내부에서 정렬알고리즘은 어떤걸 사용하고 있는지 알아보는 시간을 가져보도록 하겠습니다.

Arrays.sort()

먼저 배열을 정렬하는 Arrays.sort에 대해서 알아보도록 하겠습니다. Arrays.sort의 코드를 확인했을 때 아래와 같이 주석과 코드가 나왔습니다. 이를 통해서 보면 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)를 사용한다고 명시되어있는 것을 확인할 수 있었습니다.

/**
* 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);
}

듀얼피봇 퀵정렬은 일반적인 퀵정렬과는 다르게 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬을 진행한다고 합니다. 이 정렬방식은 랜덤 데이터에 대해서 평균적으로 퀵소트 보다 좋은 성능을 낸다고 알려져있습니다.

Collections.sort

그렇다면 이제 Collections의 정렬을 보도록 하겠습니다. Arrays.sort()랑 동일하지 않나? 라고 생각하실 수 있지만 그렇지 않습니다. Collections의 정렬과 Arrays의 정렬은 다릅니다. Collections.sort()의 코드를 따라가다보면 Arrays 클래스의 코드가 나옵니다. 하지만 사용하는 알고리즘은 다릅니다. 해당 코드를 보도록 합시다.

/**
* <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);
}

코드를 보시면 아시겠지만 레거시로 합병정렬과 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 정렬을 이용하는게 평균적으로 더 좋은 성능을 기대할 수 있다고합니다.

마무리

오늘은 자바에서 사용하는 정렬 알고리즘들에 대해서 알아보는 시간을 가져보았습니다.

Tim 정렬에 좀 더 자세히 알고 싶으신 분들은 Naver D2의 Tim sort에 대해 알아보자를 읽어보시는걸 추천드립니다.

오늘은 이걸로 마치도록 하겠습니다.

혹시 틀린 내용이 있다면 덧글로 남겨주시면 확인 후 수정하도록 하겠습니다.

감사합니다.

참조

Naver D2의 Tim sort에 대해 알아보자

stackoverflow_collections-vs-arrays-regarding-sort

secmem_special-sorts-2