여러가지 언어와 정렬 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.
방법: N (= 10,000,000)개의 정수를 입력받은 다음, 오름차순으로 정렬하는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김
입력 파일: https://github.com/Startlink/boj-sort-test
랜덤 데이터 (#12 ~ #15)
- #12 ~ #15: 1부터 N까지의 정수를 랜덤하게 섞어놓은 데이터
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
C++17 |
std::sort (array) |
775.225 |
2 |
C++17 |
std::sort (vector) |
804.8 |
3 |
C++17 |
std::stable_sort (array) |
961.9 |
4 |
C++17 |
std::stable_sort (vector) |
966.625 |
5 |
Java |
Arrays.sort |
983.55 |
6 |
C11 |
qsort |
1529.025 |
7 |
C++17 |
std::make_heap, std::sort_heap |
1695.075 |
8 |
PyPy3 |
a.sort() |
1779.3 |
9 |
PyPy |
a.sort() |
1781.25 |
10 |
PyPy3 |
a = sorted(a) |
1804.775 |
11 |
PyPy |
a = sorted(a) |
1810.45 |
12 |
C# 6.0 |
Array.Sort |
2732.255675 |
13 |
Java |
Collections.sort |
3308 |
14 |
Python 2 |
a.sort() |
5979.025 |
15 |
Python 2 |
a = sorted(a) |
6036.675 |
16 |
Python 3 |
a.sort() |
7174.65 |
17 |
Python 3 |
a = sorted(a) |
7285.95 |
18 |
C# 6.0 |
ArrayList.Sort |
9216.67275 |
19 |
C++17 |
std::multiset |
11074.925 |
20 |
C++17 |
std::map |
11470.475 |
21 |
Java |
TreeMap<Integer, Integer> |
18109.1 |
오름차순 데이터 (#1), 내림차순 데이터 (#2)
- #1: 1부터 N까지 N개의 정수가 오름차순으로 정렬되어져 있는 데이터 (
A[i] = i
)
- 1 2 3 4 5 6 ... N-2 N-1 N
- #2: 1부터 N까지 N개의 정수가 내림차순으로 정렬되어져 있는 데이터 (
A[i] = N-i+1
)
순위 (#1) |
순위 (#2) |
언어 |
출력 방법 |
#1 평균 (MS) |
#2 평균 (MS) |
1 |
1 |
PyPy3 |
a.sort() |
15 |
23.1 |
2 |
2 |
PyPy |
a.sort() |
15.2 |
23.2 |
3 |
3 |
Java |
Arrays.sort |
18.9 |
33.1 |
4 |
5 |
Java |
Collections.sort |
32.9 |
49.1 |
5 |
4 |
PyPy3 |
a = sorted(a) |
40.7 |
48.8 |
6 |
6 |
PyPy |
a = sorted(a) |
40.8 |
49.4 |
7 |
7 |
Python 3 |
a.sort() |
111 |
118.5 |
8 |
8 |
Python 2 |
a.sort() |
115.3 |
120.2 |
9 |
9 |
C++17 |
std::sort (vector) |
167 |
130 |
10 |
10 |
C++17 |
std::sort (array) |
168.4 |
131.6 |
11 |
12 |
C++17 |
std::stable_sort (vector) |
185.1 |
217.9 |
12 |
14 |
C++17 |
std::stable_sort (array) |
185.9 |
218.8 |
13 |
11 |
Python 3 |
a = sorted(a) |
204.1 |
211.8 |
14 |
12 |
Python 2 |
a = sorted(a) |
212.2 |
217.9 |
15 |
15 |
C11 |
qsort |
352 |
443.3 |
16 |
16 |
C++17 |
std::make_heap, std::sort_heap |
614.8 |
711.6 |
17 |
17 |
C# 6.0 |
Array.Sort |
1319.296 |
2316.6093 |
18 |
18 |
C# 6.0 |
ArrayList.Sort |
2839.8554 |
5081.1331 |
19 |
20 |
C++17 |
std::multiset |
6022.2 |
6179.8 |
20 |
19 |
C++17 |
std::map |
6074.5 |
6153 |
21 |
21 |
Java |
TreeMap<Integer, Integer> |
11677.3 |
11621.2 |
모든 수가 1로 같은 데이터 (#4)
- #1: N개의 정수가 모두 1인 데이터 (
A[i] = 1
)
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
PyPy3 |
a.sort() |
15 |
1 |
PyPy |
a.sort() |
15 |
3 |
Java |
Arrays.sort |
15.7 |
4 |
Java |
Collections.sort |
23.5 |
5 |
C++17 |
std::map |
25.5 |
6 |
PyPy |
a = sorted(a) |
40.9 |
7 |
PyPy3 |
a = sorted(a) |
41 |
8 |
Python 3 |
a.sort() |
97.7 |
9 |
Python 2 |
a.sort() |
101.5 |
10 |
Java |
TreeMap<Integer, Integer> |
127.9 |
11 |
C++17 |
std::sort (array) |
132.6 |
12 |
C++17 |
std::sort (vector) |
147.9 |
13 |
Python 3 |
a = sorted(a) |
152.8 |
14 |
Python 2 |
a = sorted(a) |
157.3 |
15 |
C++17 |
std::stable_sort (array) |
185.8 |
16 |
C++17 |
std::stable_sort (vector) |
186.6 |
17 |
C11 |
qsort |
352.7 |
18 |
C++17 |
std::make_heap, std::sort_heap |
731.9 |
19 |
C# 6.0 |
Array.Sort |
1539.1441 |
20 |
C# 6.0 |
ArrayList.Sort |
3774.4456 |
21 |
C++17 |
std::multiset |
6041.7 |
거의 정렬되어 있는 데이터 (#5, #6)
- #5: 1부터 N까지 N개의 정수를 오름차순으로 정렬한 다음, 10개의 쌍을 골라 위치를 서로 바꾼 데이터
- #6: 1부터 N까지 N개의 정수를 오름차순으로 정렬한 다음, 100개의 쌍을 골라 위치를 서로 바꾼 데이터
순위 (#5) |
순위 (#6) |
언어 |
출력 방법 |
#5 평균 (MS) |
#6 평균 (MS) |
1 |
1 |
Java |
Collections.sort |
65.3 |
80.7 |
2 |
2 |
PyPy3 |
a.sort() |
67.1 |
136.2 |
3 |
3 |
PyPy |
a.sort() |
72.1 |
147.1 |
4 |
4 |
PyPy3 |
a = sorted(a) |
92.4 |
162.1 |
5 |
7 |
PyPy |
a = sorted(a) |
97.8 |
169.6 |
6 |
8 |
Python 3 |
a.sort() |
153 |
180.6 |
7 |
11 |
Python 2 |
a.sort() |
166 |
194.9 |
8 |
5 |
C++17 |
std::sort (vector) |
166.2 |
167.1 |
9 |
6 |
C++17 |
std::sort (array) |
168.2 |
168.2 |
10 |
10 |
C++17 |
std::stable_sort (vector) |
188.5 |
189.7 |
11 |
9 |
C++17 |
std::stable_sort (array) |
188.7 |
189 |
12 |
15 |
Java |
Arrays.sort |
235.6 |
489.9 |
13 |
12 |
Python 3 |
a = sorted(a) |
246.8 |
274 |
14 |
13 |
Python 2 |
a = sorted(a) |
263.9 |
292 |
15 |
14 |
C11 |
qsort |
394 |
432.1 |
16 |
16 |
C++17 |
std::make_heap, std::sort_heap |
614.5 |
614.1 |
17 |
17 |
C# 6.0 |
Array.Sort |
1319.0623 |
1319.284 |
18 |
18 |
C# 6.0 |
ArrayList.Sort |
2838.8305 |
2836.1309 |
19 |
19 |
C++17 |
std::multiset |
5480.5 |
3876.9 |
20 |
20 |
C++17 |
std::map |
5567.2 |
3969.8 |
21 |
21 |
Java |
TreeMap<Integer, Integer> |
11968.4 |
11319.3 |
서로 다른 수의 개수가 적은 데이터 (#10, #11)
- #10: 1 ≤ A[i] ≤ 5, 수의 순서는 랜덤
- #11: 1 ≤ A[i] ≤ 10, 수의 순서는 랜덤
순위 (#10) |
순위 (#11) |
언어 |
출력 방법 |
#10 평균 (MS) |
#11 평균 (MS) |
1 |
1 |
C++17 |
std::map |
127.2 |
170.9 |
2 |
2 |
Java |
Arrays.sort |
137.9 |
174.9 |
3 |
3 |
C++17 |
std::sort (array) |
219.8 |
253 |
4 |
4 |
C++17 |
std::sort (vector) |
242.4 |
277.7 |
5 |
7 |
Java |
TreeMap<Integer, Integer> |
314.9 |
378.9 |
6 |
5 |
C++17 |
std::stable_sort (array) |
323.8 |
365.8 |
7 |
6 |
C++17 |
std::stable_sort (vector) |
329.4 |
372.3 |
8 |
8 |
C++17 |
std::make_heap, std::sort_heap |
640.1 |
697.2 |
9 |
10 |
PyPy3 |
a.sort() |
710.7 |
829.6 |
10 |
14 |
Java |
Collections.sort |
718.8 |
886.9 |
11 |
11 |
PyPy |
a.sort() |
721.6 |
839.3 |
12 |
9 |
C11 |
qsort |
739.9 |
818.3 |
13 |
12 |
PyPy3 |
a = sorted(a) |
740.5 |
854.9 |
14 |
13 |
PyPy |
a = sorted(a) |
745.5 |
864.5 |
15 |
15 |
Python 2 |
a.sort() |
1058.2 |
1247 |
16 |
16 |
Python 2 |
a = sorted(a) |
1103.9 |
1289.6 |
17 |
17 |
Python 3 |
a.sort() |
1150.9 |
1373.7 |
18 |
18 |
Python 3 |
a = sorted(a) |
1190.9 |
1411.5 |
19 |
19 |
C# 6.0 |
Array.Sort |
1659.6425 |
1708.063 |
20 |
20 |
C++17 |
std::multiset |
2696 |
3231.1 |
21 |
21 |
C# 6.0 |
ArrayList.Sort |
4569.8836 |
5773.6948 |
두 쌍의 위치를 바꾼 데이터 (#3)
- #3:
A[i] = i+1
(i
가 홀수), i-1
(i
가 짝수)
- 2 1 4 3 6 5 ... N-3 N-2 N N-1
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
PyPy |
a.sort() |
87.7 |
2 |
PyPy3 |
a.sort() |
88.8 |
3 |
PyPy3 |
a = sorted(a) |
113.6 |
4 |
PyPy |
a = sorted(a) |
114.2 |
5 |
C++17 |
std::sort (vector) |
148.9 |
6 |
C++17 |
std::sort (array) |
152.4 |
7 |
Java |
Collections.sort |
182 |
8 |
C++17 |
std::stable_sort (vector) |
190.9 |
9 |
C++17 |
std::stable_sort (array) |
192.2 |
10 |
Java |
Arrays.sort |
240.5 |
11 |
C11 |
qsort |
365.3 |
12 |
Python 2 |
a.sort() |
443.9 |
13 |
Python 3 |
a.sort() |
500.3 |
14 |
Python 2 |
a = sorted(a) |
540.9 |
15 |
Python 3 |
a = sorted(a) |
593.9 |
16 |
C++17 |
std::make_heap, std::sort_heap |
617.8 |
17 |
C# 6.0 |
Array.Sort |
1566.4802 |
18 |
C# 6.0 |
ArrayList.Sort |
3404.0112 |
19 |
C++17 |
std::multiset |
6341.1 |
20 |
C++17 |
std::map |
6397 |
21 |
Java |
TreeMap<Integer, Integer> |
12432.9 |
기타 데이터 (#7)
- #7:
A[i] = (i+1)/2
(i
가 홀수), (n-i/2)+1
(i
가 짝수)
- 1 N 2 N-1 3 N-2 ... N/2-1 N/2+2 N/2 N/2+1
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
C++17 |
std::stable_sort (array) |
200.3 |
2 |
C++17 |
std::stable_sort (vector) |
201.3 |
3 |
Java |
Collections.sort |
341.5 |
4 |
PyPy3 |
a.sort() |
389 |
5 |
PyPy |
a.sort() |
393.9 |
6 |
C++17 |
std::sort (array) |
414.2 |
7 |
PyPy3 |
a = sorted(a) |
418.3 |
8 |
PyPy |
a = sorted(a) |
420.4 |
9 |
C++17 |
std::sort (vector) |
421.4 |
10 |
C11 |
qsort |
530.9 |
11 |
Java |
Arrays.sort |
547.4 |
12 |
Python 2 |
a.sort() |
647.2 |
13 |
Python 3 |
a.sort() |
694.4 |
14 |
Python 2 |
a = sorted(a) |
745.9 |
15 |
C++17 |
std::make_heap, std::sort_heap |
759.9 |
16 |
Python 3 |
a = sorted(a) |
788.1 |
17 |
C# 6.0 |
Array.Sort |
1984.1046 |
18 |
C# 6.0 |
ArrayList.Sort |
4247.6797 |
19 |
C++17 |
std::multiset |
4732.6 |
20 |
C++17 |
std::map |
4870 |
21 |
Java |
TreeMap<Integer, Integer> |
12020.5 |
기타 데이터 (#8)
- #8:
A[i] = (2500*((i-1)%5))+((i-1)/5)+1
- 1 2501 5001 7501 10001 2 2502 5002 7502 10002 ...
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
C++17 |
std::stable_sort (array) |
203.3 |
2 |
C++17 |
std::stable_sort (vector) |
204.8 |
3 |
C++17 |
std::sort (array) |
302.5 |
4 |
C++17 |
std::sort (vector) |
310.9 |
5 |
PyPy |
a.sort() |
378.6 |
6 |
PyPy3 |
a.sort() |
382.7 |
7 |
PyPy3 |
a = sorted(a) |
389.5 |
8 |
PyPy |
a = sorted(a) |
407.1 |
9 |
Java |
Collections.sort |
477.2 |
10 |
C11 |
qsort |
517.9 |
11 |
Java |
Arrays.sort |
621.1 |
12 |
C++17 |
std::make_heap, std::sort_heap |
879.1 |
13 |
Python 2 |
a.sort() |
1016.8 |
14 |
Python 2 |
a = sorted(a) |
1111.7 |
15 |
Python 3 |
a.sort() |
1133.4 |
16 |
Python 3 |
a = sorted(a) |
1228.6 |
17 |
C# 6.0 |
Array.Sort |
2001.892 |
18 |
C++17 |
std::map |
3123.3 |
19 |
C# 6.0 |
ArrayList.Sort |
4106.3872 |
20 |
Java |
TreeMap<Integer, Integer> |
4692 |
21 |
C++17 |
std::multiset |
4718.6 |
기타 데이터 (#9)
- #9:
A[i] = (i-1)%10+1
- 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 ...
순위 |
언어 |
출력 방법 |
평균 (MS) |
1 |
C++17 |
std::map |
40.6 |
2 |
Java |
Arrays.sort |
185.3 |
3 |
C++17 |
std::sort (array) |
198.4 |
4 |
C++17 |
std::stable_sort (array) |
201.3 |
5 |
C++17 |
std::stable_sort (vector) |
204.9 |
6 |
C++17 |
std::sort (vector) |
221.7 |
7 |
Java |
TreeMap<Integer, Integer> |
231.7 |
8 |
Java |
Collections.sort |
404.9 |
9 |
PyPy3 |
a.sort() |
503.7 |
10 |
PyPy |
a.sort() |
508.3 |
11 |
PyPy3 |
a = sorted(a) |
531 |
12 |
PyPy |
a = sorted(a) |
536.1 |
13 |
C11 |
qsort |
601.5 |
14 |
C++17 |
std::make_heap, std::sort_heap |
650.4 |
15 |
Python 2 |
a.sort() |
959.8 |
16 |
Python 2 |
a = sorted(a) |
997.2 |
17 |
Python 3 |
a.sort() |
1039.1 |
18 |
Python 3 |
a = sorted(a) |
1080.6 |
19 |
C# 6.0 |
Array.Sort |
1665.0063 |
20 |
C++17 |
std::multiset |
5437.9 |
21 |
C# 6.0 |
ArrayList.Sort |
6177.1008 |
언어 정보
- C11
gcc (GCC) 7.2.0
gcc a.c -o bin/a -O2 -std=c11
- C++17
g++ (GCC) 7.2.0
g++ a.cpp -o bin/a -O2 -std=c++17
- Java
javac 1.8.0_151
javac Main.java
- Python 2
Python 2.7.14
python a.py
- PyPy
PyPy 5.10.0 with GCC 6.2.0 20160901
pypy a.py
- Python 3
Python 3.6.3
python3 a.py
- PyPy3
PyPy 5.10.0 with GCC 6.2.0 20160901
pypy3 a.py
- C# 6.0
Mono C# compiler version 4.2.1.0
mcs -codepage:utf8 -warn:0 -optimize+ -checked+ -clscheck- -reference:System.Numerics.dll Main.cs
mono --optimize=all Main.exe
댓글 (8개) 댓글 쓰기
sgchoi5 5년 전
수고하셨습니다 : )
upple1 5년 전
여기서 c++의 map은 중복된 값들은 포함되지 않는건가요?
bupjae 5년 전
map은 key-value pair 니까, value 를 count 목적으로 쓴 것으로 보입니다.
upple1 5년 전
와 그렇게 했구나 생각을 못했네
bupjae 5년 전
1) 혹시 사용한 프로그램 코드도 github에 올려주실 수 있나요? 2) golang의 sort.Ints도 측정할 수 있나요?
baekjoon 5년 전
tuna 5년 전
c언어 컴파일 옵션이 이상해요;; c11인데 컴파일 옵션은 c99에요ㅠㅠ
baekjoon 5년 전
글 내용을 수정했습니다.