퀵 정렬 (Java7 이후 Arrays.sort()메서드의 Dual Pivot Quick Sort)

•  
•  
• 퀵 정렬(Quick Sort)
•  
• 피봇(Pivot)을 선택해 피봇보다 작은 그룹과 큰 그룹으로 나누는 작업을 반복하여 정렬하는 방식
  
  장점
• 기준값에 의한 분할을 통해서 구현하는 정렬법으로써, 분할 과정에서 logN 이라는 시간이 걸리게되고 전체적으로 보게 되면 평균 NlogN 으로써 실행시간이 준수한 편이다.
• 
  단점
• 기준값(Pivot)에 따라서 시간복잡도가 크게 달라진다. Pivot이 적당하게 이상적인 값을 선택했다면 NlogN의 시간복잡도를 갖지만, 최악으로 Pivot을 선택할 경우 O(N^2)이라는 시간복잡도를 갖게 된다.

Java의 Arrays.sort() 메서드는 기본적으로 Dual-Pivot Quicksort 알고리즘을 사용합니다. 이는 Java 7 이후 버전부터 도입되었습니다.

 

그러나 Java 7 이전의 경우, Arrays.sort()는 Merge Sort 알고리즘을 사용했습니다. Java 7에서는 정렬 알고리즘을 Dual-Pivot Quicksort로 변경하여 성능을 개선했습니다.

 

또한, 작은 크기의 배열에 대해서는 Insertion Sort가 사용될 수 있습니다. 따라서 Java의 Arrays.sort() 메서드는 다양한 상황에 따라 최적의 정렬 알고리즘을 선택하여 사용합니다.