Java sort() Arrays와 Collections

Java의 정렬 내장 함수

Arrays.sort() 와 Collections.sort()는 서로 다른 정렬 알고리즘으로 구현

int[] array = new int[]{1, 3 , 5, 4, 2};
Arrays.sort(array);

List<Integer> collection = new ArrayList<>(List.of(1, 3, 5, 4, 2));
Collections.sort(collection);

 

Arrays.sort()

Arrays.sort() 확인했을 때, 듀얼피봇 퀵정렬(Dual-Pivot QuickSort) 확인

듀얼피봇 퀵정렬(Dual-Pivot QuickSort)

• 피봇을 2개를 두고 3개의 구건을 만들어 퀵 정렬 진행하는 알고리즘
• 퀵소트보다 좋은 성능

 

Collections.sort()

• nlg(n) 비교보다 훨씬 적은 수의 비교를 필요로 하는 안정적인 적응형 반복 병합 정렬
• 입력 배열이 무작위로 정렬될 때 기존 병합 정렬의 성능
• Tim Peter 에 의해 고안된 Insertion Sort, Merge Sort가 혼용 된 하이브리드 정렬 사용

 Timsort

삽입 정렬과 합병정렬을 결합하여 만든 정렬로 합병정렬을 기반으로 구현하되, 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입 정렬을 수행한다. Quick Sort의 경우 분명 일반적으로 빠르긴 하지만, 특정 상태(정렬 된 상태)에서는 급격히 성능이 떨어지게 된다. 가장 안정적이면서 비교비용이 비쌀 경우에도 이득을 볼 수 있는 병합 정렬이 적절해 보인다. Merge Sort는 안정 정렬이 가능하기 때문에 현실 데이터에 대해 더욱 알맞은 정렬 방법이기도 하다.

Tim Sort에서는 일정 사이즈의 부분 리스트를 얻고(divide), 각각의 부분리스트들에 대해 삽입정렬을 수행하며 정렬을 하며(sort), 정렬 된 부분리스트들을 다시 합치는 방식(conqure)을 사용하게 된다.

 

 

참고

자바 [JAVA] - 팀 정렬 (Tim Sort)