[JAVA] Arrays.sort 와 Collections.sort의 차이

안녕하세요.

오늘은 자바의 Arrays.sort와 Collections.sort의 차이에 대해 써보려고 합니다.

 

저는 블로그에 학습한 기록을 정리하는 것에 큰 의미를 두는 편이 아니라 그동안 노션에만 정리해왔었는데요.

저빼고 다 블로그 하고 있길래 시작합니다. . .

1일 1블챌... 레츠꼬. . .

 

아무튼.

 

 

 

 

 

 

궁금하게된 이유

Arrays.sort와 Collections.sort의 차이에 대해 궁금해하게 됐던 이유는,

알고리즘 문제를 풀던 도중

Collections.sort는 시간 초과가 나는데 Arrays.sort는 시간 초과가 나지 않아서였습니다.

 

 

 

 

 

왜 Collections.sort가 Arrays.sort보다 성능이 좋을까?

결론을 먼저 말하자면,

Arrays.sort는 Dual-Pivot Quicksort를 사용하고( 기본 타입을 정렬할 때  )

Collections.sort는 Timsort 알고리즘을 사용하기 때문입니다.

 

 

 

 

 

Timsort  알고리즘

합병 정렬과 삽입 정렬을 조합하여 구현되었습니다.

최악의 경우 O(nlogn)의 시간 복잡도를 갖습니다.

 

 

 

 

 

 

Dual Pivot Quicksort 알고리즘

Arrays.sort()가 기본타입 배열(int[], double[])을 정렬할 때 사용됩니다.

최악의 경우 O(n²)의 시간 복잡도를 갖습니다.

 

동작 방식은 다음과 같습니다.

 

1. 피벗 선택

    피벗을 선택합니다.

2. 파티션 분할

    피벗을 기준으로 배열을 3부분으로 나눕니다.

3. 재귀 호출

    각 부분에 대해 재귀적으로 정렬을 수행합니다.

4. 병합

   재귀 호출이 끝난 정렬된 결과를 병합합니다.

 

 

 

 

 

 

 

마무리

기본타입을 정렬한다면, Arrays.sort는 최악의 경우 O(n²)의 시간 복잡도를 갖습니다.

기본타입 정렬 시 Dual Pivot Quicksort알고리즘을 사용하기 때문입니다.

 

Collections.sort(=List.sort)는 최악의 경우 O(nlogn)의 시간 복잡도를 갖습니다.

Timsort알고리즘을 사용하기 때문입니다.

 

 

주의

객체 정렬이라면, Arrays.sort도 Timsort 알고리즘을 사용합니다.

객체 정렬 시, 두 메서드의 성능차이는 없습니다!