[정렬] 정렬 문제 풀이 및 속도 비교
■ 정렬의 속도 / 메모리 사용 비교
- 미니멈이 1이고, 맥시멈이 백만인 숫자를 입력받아 정렬한다고 할 때, 어떤 정렬을 쓰는게 좋을까....?
- 문제를 풀어본 결과, Merge sort가 가장 빨랐고, 그 다음에 Arrays.sort, 그 다임이 Quck Sort 였다.
- 그럼 Arrays.sort는 무슨 정렬을 사용하는 걸까...
https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
■ Collections와 Arrays의 Sort 메소드가 사용하는 정렬방식
[1] Arrays.sort() : 듀얼 피봇 퀵정렬 (Dual-Pivot QuckSort)
[2] Collections.sort() : Tim 정렬 (삽입 정렬 + 합병정렬을 결합한 방식)
https://sabarada.tistory.com/138
[Java] Java의 정렬 알고리즘 - Arrays와 Collections
안녕하세요. 오늘 포스팅은 Java의 Collection에서 사용하고 있는 정렬에 대해서 알아보려고 합니다. Java를 사용하다보면 정렬해서 처리해야할 경우가 생깁니다. 그럴경우 아래와 같이코드를 작성
sabarada.tistory.com
■ 결론
- 위 문제에서는 결국, 병합정렬을 사용할 때 가장 빠르고, 그 다음에 듀얼 피봇 퀵정렬을 사용할 때 빨랐다.
- 퀵 정렬은 오히려 시간이 오래 걸려 시간 초과가 나타났다.