Java에서 사용하는 정렬(sort) 메소드는 무슨 알고리즘을 사용할까?

정렬 방법

Java에서 정수를 오름차순으로 정렬할 수 있는 방법을 찾아봤습니다.

1. int[] -> Arrays.sort()를 사용하여 정렬

2. List<Integer> -> Collections.sort()를 사용하여 정렬

 

Arrays.sort(int[] a)

Dual-Pivot Quicksort 사용

 

참고 : https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-int:A

Arrays (Java Platform SE 8 )

 

Dual-Pivot Quicksort

평균적인 시간 복잡도 : 시간 복잡도 O(n log n)
안정적이지 않음

두 개의 피벗을 선택하여 배열을 세 부분(피벗보다 작은 값, 두 피벗 사이의 값, 피벗보다 큰 값)으로 분할한 뒤 재귀적으로 정렬하는 방식

List<Integer>

TimSort 사용

참고 : https://docs.oracle.com/javase/8/docs/api/

Java Platform SE 8

 

Timsort

최악 시간 복잡도 : O(n log n)

최선의 시간 복잡도 : O(n) <- 정렬된 부분이 많은 경우

안정적

Merge Sort와 Insertion Sort의 장점을 결합한 하이브리드 알고리즘

 

1. 런(Run) 탐색: 원소가 이미 정렬된 부분 배열(런, Run)을 찾는다.

2. Merge Sort 사용: 일정 크기 이상의 정렬되지 않은 부분을 병합 정렬 방식으로 정렬(특정 조건을 충족하는 경우에만 병합)

3. Insertion Sort 사용: 작은 크기의 배열에 대해 삽입 정렬을 사용하여 최적화 

 

---

"안정적이다"란 무엇인가?

안정적이란 것은 예를 들어 [90(A), 30, 40, 60, 90(B)] 이라는 배열을 정렬하고자 할때,

90이라는 정수가 2개가 있는 것을 볼 수 있습니다.

안정적으로 정렬된다 함은 [90(A), 90(B), 60, 40, 30]과 같이 배열에 있던 순서 그대로 유지하는 것입니다.

안정적이지 않은 상태로 정렬되는 것은 [90(B), 90(A), 60, 40, 30]과 같이 정렬되는 것입니다.