정렬 속도 비교

2018년 2월 16일
baekjoon
댓글 (8개)
정렬

여러가지 언어와 정렬 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.

방법: 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)
- N N-1 N-2 N-3 ... 3 2 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)
- 1 1 1 1 1 1 ... 1 1 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