💡 <Java에서의 정렬알고리즘>
Primitive Type → QuickSort [nlogn]
Object Type → MergeSort [nlogn]MergeSort
- 시간복잡도: O(nlogn)
- 크게 split단계와 merge단계로 나눌 수 있다.
- 재귀를 사용한다.
- merge단계에서는 두개의 리스트의 각각 A[0]과 B[0]을 비교해서 작은 값을 앞으로 보내고, 작은값이 포함되어있던 리스트의 피벗? 비교대상인덱스? 를 다음으로 넘긴다.
- ex. A[0]과 B[0]중 B가 더 작으면, B[0]을 앞으로 보내고, 다음에는 A[0]과 B[1]을 비교한다.
QuickSort
- 시간복잡도: O(nlogn)
- 피벗을 사용함
- 재귀를 사용한다.
- 맨 앞을 피벗으로 설정해서 작은데이터를 왼쪽, 큰 데이터를 오른쪽으로 넘긴다. 이를 반복한다.
정렬알고리즘 코드 예시
