[Java API] 정렬 메서드(sort) 종류와 차이점

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A0%AC-%EC%A0%95%EB%A6%AC-%EB%B0%8F-%EC%84%A0%ED%83%9D-%EB%A7%A4%EB%89%B4%EC%96%BC

[알고리즘] 정렬 정리 및 선택 매뉴얼

먼저 위 포스트를 통해 정렬에 대한 기본적인 공부를 하고 오는 것을 추천한다

 

자바에서 Primitive Type(int, long 등)의 경우에는 이중-피벗 Quick 정렬 기반의 정렬 알고리즘을 사용하고, Reference Type(Int, Long 등 Object를 상속받는 모든 클래스)의 정렬은 Tim-Sort 알고리즘(삽입정렬 + 병합정렬)을 사용한다. Quick Sort의 경우 최악의 케이스에서 O(N^2)의 시간복잡도를 보여주므로, 만약 ps에서 저격 데이터가 있는 경우 시간초과가 발생할 수 있다. 반면에, Tim-Sort의 경우 최악의 케이스에서도 O(NlogN)이 보장되므로 저격 데이터가 존재할 수 없다.

자바에서 저렇게 타입에 따라 2가지 정렬 방식을 사용하는 이유는 "stable", "unstable" sort의 차이이다. Primitive Type은 값이 동일하면 구분되지 않지만, Reference Type의 경우 모든 객체는 Value가 동일하여도 구분이 가능하므로, Primitive Type은 unstable sort 인 Quick Sort로,Reference Type은 stable sort 인 Tim-Sort로 정렬하는 것이다.

 

• Dual-Pivot Quicksort: 빠르지만 최악의 경우 O(n^2) + "unstable"
• TimSort: 실용적이고 효율적이며, O(n log n)의 성능을 제공 + "stable"

(데이터가 자연에서 존재하는 일반적인 케이스로 들어온다면, 평균적으로 Dual-Pivot Quick Sort 가 Tim-Sort 보다 빠른 성능을 보여준다)

 

 

 

[Java 정렬 메서드]

1. Arrays.sort()

• 정렬 대상: 기본 타입 배열 (int[], char[], etc.) 또는 Comparable 인터페이스를 구현한 객체 배열.
• 알고리즘: Dual-Pivot Quicksort (Java 7부터 사용됨)
• 특징:
  • 평균적으로 O(n log n)의 시간 복잡도를 가짐.
  • 대부분의 경우에 매우 빠르게 동작하지만, 최악의 경우 O(n^2)의 성능을 보일 수 있음.
  • 그러나 실제 구현에서는 이러한 최악의 경우를 줄이기 위해 많은 최적화가 되어 있음.

2. Arrays.sort(Object[] a, Comparator c)

• 정렬 대상: Comparator 인터페이스를 사용하는 객체 배열.
• 알고리즘: TimSort
• 특징:
  • Comparator를 사용하여 객체의 정렬 기준을 커스터마이징 가능.
  • TimSort는 삽입 정렬과 병합 정렬을 혼합한 알고리즘으로, 정렬된 데이터 또는 부분적으로 정렬된 데이터에 대해 매우 효율적임.
  • 시간 복잡도는 O(n log n).

3. Collections.sort(List<T> list)

• 정렬 대상: List 인터페이스를 구현한 객체 (예: ArrayList, LinkedList)
• 알고리즘: TimSort
• 특징:
  • List 인터페이스를 구현한 객체들을 정렬.
  • 내부적으로 Arrays.sort() 메서드를 호출하여 List를 배열로 변환한 후 정렬 작업을 수행함.
  • 따라서 O(n log n)의 시간 복잡도를 가짐.
  • List는 인덱스가 있는 데이터 구조이기 때문에 랜덤 액세스가 가능함.

4. Collections.sort(List<T> list, Comparator<? super T> c)

• 정렬 대상: Comparator를 사용하는 List.
• 알고리즘: TimSort
• 특징:
  • Comparator 인터페이스를 사용하여 정렬 기준을 제공할 수 있음.
  • List의 정렬 순서를 사용자 정의할 수 있으며, 역시 O(n log n)의 시간 복잡도를 가짐.

•  

 

 

 

[선택 가이드]

**Collections.sort(list)**

- 리스트는 순서가 있는 컬렉션이므로 정렬할 수 있다.

- 이 메서드를 사용하면 기본 정렬이 적용된다.

- 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 'list.sort()' 사용을 더 권장한다. 참고로 둘의

결과는 같다.

 

**Collections.sort(list, new IdComparator())**

- 별도의 비교자로 비교하고 싶다면 다음 인자에 비교자를 넘기면 된다.

- 하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 'list.sort()' 사용을 더 권장한다. 참고로 둘의

결과는 같다.

 

 

**list.sort(null)**

- 별도의 비교자가 없으므로 'Comparable'로 비교해서 정렬한다.

- 자연적인순서로비교한다.

- Java 1.8 부터 사용

 

**list.sort(new IdComparator())**

- 전달한 비교자로 비교한다.

- Java 1.8 부터 사용

 

 

 

 

 

 

 

따라서 "Java 버전이 1.8 미만이면 Collections.sort()를 이용하면 되고, 그게 아니라면 list.sort()를 이용하는 것이 좋다"

 

 

참고 및 출처: 김영한의 실전 자바 - 중급 2편

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2