1 | /* -*- C++ -*- |
---|

2 | * |
---|

3 | * This file is a part of LEMON, a generic C++ optimization library |
---|

4 | * |
---|

5 | * Copyright (C) 2003-2008 |
---|

6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|

7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|

8 | * |
---|

9 | * Permission to use, modify and distribute this software is granted |
---|

10 | * provided that this copyright notice appears in all copies. For |
---|

11 | * precise terms see the accompanying LICENSE file. |
---|

12 | * |
---|

13 | * This software is provided "AS IS" with no warranty of any kind, |
---|

14 | * express or implied, and with no claim as to its suitability for any |
---|

15 | * purpose. |
---|

16 | * |
---|

17 | */ |
---|

18 | |
---|

19 | #define NDEBUG |
---|

20 | |
---|

21 | #include <lemon/time_measure.h> |
---|

22 | #include <lemon/smart_graph.h> |
---|

23 | #include <lemon/graph_utils.h> |
---|

24 | #include <lemon/maps.h> |
---|

25 | #include <lemon/error.h> |
---|

26 | |
---|

27 | #include <lemon/radix_sort.h> |
---|

28 | |
---|

29 | #include <lemon/random.h> |
---|

30 | |
---|

31 | #include <vector> |
---|

32 | #include <algorithm> |
---|

33 | #include <cmath> |
---|

34 | |
---|

35 | using namespace std; |
---|

36 | using namespace lemon; |
---|

37 | |
---|

38 | void testRadixSort() { |
---|

39 | int n = 10000000; |
---|

40 | vector<int> data(n); |
---|

41 | for (int i = 0; i < n; ++i) { |
---|

42 | data[i] = rnd[1000] - 500; |
---|

43 | } |
---|

44 | radixSort(data.begin(), data.end()); |
---|

45 | } |
---|

46 | |
---|

47 | |
---|

48 | void testCounterSort() { |
---|

49 | int n = 10000000; |
---|

50 | vector<int> data(n); |
---|

51 | for (int i = 0; i < n; ++i) { |
---|

52 | data[i] = rnd[1000] - 500; |
---|

53 | } |
---|

54 | counterSort(data.begin(), data.end()); |
---|

55 | } |
---|

56 | |
---|

57 | void testSort() { |
---|

58 | int n = 10000000; |
---|

59 | vector<int> data(n); |
---|

60 | for (int i = 0; i < n; ++i) { |
---|

61 | data[i] = rnd[1000] - 500; |
---|

62 | } |
---|

63 | sort(data.begin(), data.end()); |
---|

64 | } |
---|

65 | |
---|

66 | void testStableSort() { |
---|

67 | int n = 10000000; |
---|

68 | vector<int> data(n); |
---|

69 | for (int i = 0; i < n; ++i) { |
---|

70 | data[i] = rnd[1000] - 500; |
---|

71 | } |
---|

72 | stable_sort(data.begin(), data.end()); |
---|

73 | } |
---|

74 | |
---|

75 | void testSorts() { |
---|

76 | { |
---|

77 | int n = 10000000; |
---|

78 | vector<int> data(n); |
---|

79 | } |
---|

80 | cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl; |
---|

81 | cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl; |
---|

82 | cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl; |
---|

83 | cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl; |
---|

84 | } |
---|

85 | |
---|

86 | |
---|

87 | int main() { |
---|

88 | testSorts(); |
---|

89 | return 0; |
---|

90 | } |
---|