Java Sort Algorithm

 

Java에서 정렬을 수행하는 두 가지 주요 방법은 Arrays.sort()와 Collections.sort()이다.

Arrays.sort()는 배열을 정렬할 때, Collections.sort()은 자료구조의 정렬 시 사용한다.

이 두개는 다른 정렬방식으로 구현된다.

Arrays.sort()

Arrays.sort의 코드는 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)을 사용한다.

아래는 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);
}

듀얼피봇 퀵정렬은 일반적인 퀵정렬과는 다르게 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬을 진행한다.

랜덤 데이터에 대해서 평균적으로 퀵정렬 보다 좋은 성능을 낸다.

 

 

Collections.sort

Collections.sort는 합병정렬과 Tim 정렬을 사용한다. 

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

Tim 정렬은 삽입(Insertion) 정렬과 합병(Merge) 정렬을 결합하여 만든 정렬이다.

 

 

왜 서로 다른 알고리즘을 사용하는가?

다른 알고리즘을 사용하는 이유는 참조 지역성 원리(Local of Reference)에 있다. 

참조 지역성의 원리란 동일한 값 또는 해당 값의 근처에 있는 스토리지 위치가 자주 액세스되는 특성을 말한다.

그렇기에 CPU 캐싱 시, 해당 데이터만이 아니라 인접한 메모리에 있는 데이터 또한 캐시 메모리에 함께 저장한다.

 

정렬 알고리즘 실제 동작시간 : T(n)=C⋅f(n)+a

• T(n): 입력 크기 n에 대한 실행 시간
• C: 알고리즘의 특정한 구현에서 수행되는 기본적인 작업(비교, 교환 등)당 소요되는 시간
• f(n): 입력 크기 n에 대한 알고리즘의 시간 복잡도 함수
• a: 입력 크기 n에 대한 다른 영향을 받는 상수

참조 지역성 원리는 C에 영향을 미친다.

Array는 메모리적으로 각 값들이 연속적인 주소를 가지고 있기 때문에 C의 값이 낮다. 

그래서 참조 지역성이 좋은 퀵 정렬을 이용하면 충분한 성능을 제공할 수 있다.

하지만 Collection은 연속적으로 값이 할당되지 않는 LinkedList도 존재한다.

따라서 참조 인접성이 좋지 않고 C의 값이 상대적으로 높다. 

이럴 때 퀵 정렬 보다는 합병정렬과 삽입정렬을 병합한 Tim 정렬이 평균적으로 더 좋은 성능을 기대할 수 있다고 한다.