0314 TIL (오늘 하루 정리)

| 0314

📑 공부한 내용

• 코딩테스트
  • 코딩테스트 전형 참여
  • 조합 / 순열 관련 Java 코드 구현 및 정리
  • 정렬 정리
• Arrays.sort() 
  • Wrapper Type일 경우 -> legacyMergeSort, ComparableTimSort 알고리즘 적용
  • Primitive Type일 경우 -> DualPivotQuickSort 알고리즘 적용

Wrapper Type일 경우 Arrays.sort()

Primitive Type일 경우 Arrays.sort()

• Collections.sort()
  • 내부를 확인하면, legacyMergeSort()와 TimSort() 알고리즘 적용

• TimSort 알고리즘

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

In the worst case, Timsort takes comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.
- wikipedia

• DualPivotQuickSort 알고리즘 -> 평균의 경우 : O(nlogn) / 최악의 경우 : O(n^2)
• Timsort 알고리즘 -> 평균의 경우 : O(nlogn) / 최악의 경우 : O(nlogn)

 

• 근데 왜 DualPivotQuickSort 알고리즘을 Object타입 정렬에 사용하지 않는가?
  • 정렬 안정성 때문이다. DualPivotQuickSort는 일반 QuickSort와 같이 정렬 안정성을 보장해주지 않는다고 한다.
  • 이해 부족 -> 추가 공부 예정

 

📖 하루 정리

•  기초부터 하나씩 다시 정리중!