정렬 속도 비교

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

방법: 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

댓글 (8개) 댓글 쓰기


sgchoi5 6년 전

수고하셨습니다 : )


upple1 6년 전

여기서 c++의 map은 중복된 값들은 포함되지 않는건가요?


bupjae 6년 전

map은 key-value pair 니까, value 를 count 목적으로 쓴 것으로 보입니다.


upple1 6년 전

와 그렇게 했구나 생각을 못했네


bupjae 6년 전

1) 혹시 사용한 프로그램 코드도 github에 올려주실 수 있나요? 2) golang의 sort.Ints도 측정할 수 있나요?


baekjoon 6년 전

  1. 올릴 예정입니다.
  2. golang도 gitihub에 올리면서 측정해서 업데이트하겠습니다.

tuna 6년 전

c언어 컴파일 옵션이 이상해요;; c11인데 컴파일 옵션은 c99에요ㅠㅠ


baekjoon 5년 전

글 내용을 수정했습니다.