티스토리 뷰
728x90
반응형
Arrays.sort(double[]), Arrays.sort(int[]), Arrays.sort(char[]), Arrays.sort(long[]), Arrays.sort(float[]), Arrays.sort(byte[]) : DualPivotQuicksort (JDK 7)
Collections.sort(List), Collection.sort(List, Comparator), Arrays.sort(Object[]) :
Collections.sort는 Arrays.sort를 호출하여
Arrays.legacyMergeSort, ComparableTimSort 사용
시간 복잡도
| Timsort | Introsort | Merge sort | Quicksort | Insertion sort | Selection sort | Smoothsort | |
| Best case | O(n) | O(n log n) | O(n log n) | O(n) | O(n^2) | O(n) | |
| Average case | O(n log n) | O(n log n) | O(n log n) | O(n log n) | O(n^2) | O(n^2) | O(n log n) |
| Worst case | O(n log n) | O(n log n) | O(n log n) | O(n^2) | O(n^2) | O(n^2) | O(n log n) |
공간 복잡도
| Timsort | Merge sort | Quicksort | Insertion sort | Selection sort | Smoothsort | |
| Space complexity | O(n) | O(n) | O(log n) | O(1) | O(1) | O(1) |
* 출처
http://iloveulhj.github.io/posts/java/java-collection-sort.html
728x90
반응형
'Java' 카테고리의 다른 글
| Arrays binarySearch() vs HashMap (0) | 2020.02.14 |
|---|---|
| String split() vs StringTokenizer (0) | 2020.02.12 |
| Comparable vs Comparator (0) | 2020.02.06 |
| Iterator (0) | 2020.02.04 |
| String VS StringBuilder VS StringBuffer (0) | 2019.10.19 |
반응형
300x250