Arrays.sort에 관한 간단한 고찰

왜??

코테연습하다가 Arrays.sort를 사용해야 하는데 시간초과가 나서 이를 좀더 알아보기 위해....

sort

보편적으로 배열을 정렬할 땐 Arrays.sort(), 컬렉션(List,Set..)을 정렬할 땐 Collections.sort()를 사용한다.
찾아보니 같은 sort 메서드지만 내부에서는 다른 정렬방식을 사용하여 정렬한다고 한다.

	방식	시간복잡도
Arrays.sort	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort	평균, 최악 : O(nlog(n))

두가지 에서 사용하는 정렬 방식이 다르다.
Timesort란 삽입정렬과 합병정렬을 합친 방식이다.

우선순위 큐

자바에는 자료구조 heap을 구현한 우선순위 큐 클래스가 있다.

큐를 생각해보면 가장 먼저 들어온 요소가 가장 먼저 나가게 되는데, 우선순위 큐에서는 요소들이

우선순위를 가져서 들어온 순서와 상관없이 우선순위가 높은 요소가 큐에서 가장 먼저 나가게 된다.

이때 나오는 요소는 우선순위가 가장 높은 heap 자료구조의 최상단 root node이다.

우선순위 큐에서의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다.

• upHeap

삽입시 가장 마지막 위치에 요소를 추가시킨 후 부모 노드와의 비교 후 Swap 과정을 통해 알맞은 위치를 찾아간다.

• downHeap

삭제 시 root node를 반환 후 가장 마지막 요소를 root node에 위치시킨 후 자손과의 비교를 통해 Swap 과정을 거쳐

알맞은 위치를 찾아간다.

자손과의 Swap은 둘 중 우선순위가 큰 node와 Swap한다.

큐와 비슷한 성질을 이용하지만, 큐에서는 front 요소의 반환 시간은 O(1)이다. 하지만 우선순위 큐에서는 가장 우선순위가

높은 값을 가져온 후 완전 이진트리로 다시 만드는 과정인 Swap 과정 때문에 O(logN)이 걸린다.