[Java] Arrays.sort(), Collections.Sort() 속도 비교

알고리즘 문제를 풀며 이론적으로는 $O(n\log n)$의 시간 복잡도를 가진다고 알고 있던 정렬 함수들이 컬렉션의 종류에 따라 같은 코드지만 시간 차이가 많이 나는 것을 보고 실제 시간이 얼마나 차이 나는지 알아보기 위해 테스트를 진행해 보았다.

하는김에 PriorityQueue와 TreeMap도 얼마나 걸리는지 궁금해서 함께 테스트했다.

 

모두 같은 코드로 구성되어 있으며, 테스트데이터만 변경하면서 실험해 보았다. 같은 데이터로 10회 반복해 평균을 낸 시간을 정리했다.

 

• 버전 : Java 15
• 코드 : Github
• 테스트 데이터 : 출처 - Startlink/boj-sort-test

 

1️⃣ 이미 정렬되어있는 데이터

1부터 10,000,000까지의 숫자가 오름차순 정렬되어있는 데이터

 

2️⃣ 역순으로 정렬된 데이터

1부터 10,000,000까지의 숫자가 내림차순 정렬되어있는 데이터

 

3️⃣ 랜덤 데이터

1부터 10,000,000까지의 숫자 10,000,000개가 랜덤하게 섞여있는 데이터

 

4️⃣ 다른 수가 적은 데이터

1부터 10까지의 숫자가 랜덤하게 10,000,000개 있는 데이터

 

---

❓ 왜 차이가 발생할까

Arrays.sort()는 Dual-Pivot Quicksort로 구현되어 있으며, 모든 데이터 타입에서 $O(n\log n)$의 시간 복잡도를 제공한다고 한다.

 

Collections.sort()는 내부 구현을 보면 List를 Array로 변경한 뒤 merge sort를 변형한 TimSort를 사용한다고 한다. 시간 복잡도는 $O(n\log n)$으로 Arrays.sort()와 동일하다.

하지만 Collections.sort()는 T[](Boxed)의 배열의 형태를 가지고 있기때문에 unwrap한 뒤 재정렬하기 때문에 오버헤드가 발생해 느리지만 stable하다(같은 값일 경우 위치를 바꾸지 않음)는 장점도 존재한다.

 

 

 

 

 

 

---

📚 Reference

https://stackoverflow.com/questions/52714131/why-is-collections-sort-much-slower-than-arrays-sort
https://docs.oracle.com/en/java/javase/15/docs/api/index.html
https://github.com/Startlink/boj-sort-test