author | ladanyi |
Sat, 17 Dec 2005 21:51:10 +0000 | |
changeset 1861 | 5f204c7a1318 |
child 1956 | a055123339d5 |
permissions | -rw-r--r-- |
deba@1833 | 1 |
#define NDEBUG |
deba@1833 | 2 |
|
deba@1833 | 3 |
#include <lemon/time_measure.h> |
deba@1833 | 4 |
#include <lemon/smart_graph.h> |
deba@1833 | 5 |
#include <lemon/graph_utils.h> |
deba@1833 | 6 |
#include <lemon/maps.h> |
deba@1833 | 7 |
#include <lemon/error.h> |
deba@1833 | 8 |
|
deba@1833 | 9 |
#include <lemon/radix_sort.h> |
deba@1833 | 10 |
|
deba@1833 | 11 |
#include <vector> |
deba@1833 | 12 |
#include <algorithm> |
deba@1833 | 13 |
#include <cmath> |
deba@1833 | 14 |
|
deba@1833 | 15 |
using namespace std; |
deba@1833 | 16 |
using namespace lemon; |
deba@1833 | 17 |
|
deba@1833 | 18 |
void testRadixSort() { |
deba@1833 | 19 |
int n = 10000000; |
deba@1833 | 20 |
vector<int> data(n); |
deba@1833 | 21 |
for (int i = 0; i < n; ++i) { |
deba@1833 | 22 |
data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
deba@1833 | 23 |
} |
deba@1833 | 24 |
radixSort(data.begin(), data.end()); |
deba@1833 | 25 |
} |
deba@1833 | 26 |
|
deba@1833 | 27 |
|
deba@1833 | 28 |
void testCounterSort() { |
deba@1833 | 29 |
int n = 10000000; |
deba@1833 | 30 |
vector<int> data(n); |
deba@1833 | 31 |
for (int i = 0; i < n; ++i) { |
deba@1833 | 32 |
data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
deba@1833 | 33 |
} |
deba@1833 | 34 |
counterSort(data.begin(), data.end()); |
deba@1833 | 35 |
} |
deba@1833 | 36 |
|
deba@1833 | 37 |
void testSort() { |
deba@1833 | 38 |
int n = 10000000; |
deba@1833 | 39 |
vector<int> data(n); |
deba@1833 | 40 |
for (int i = 0; i < n; ++i) { |
deba@1833 | 41 |
data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
deba@1833 | 42 |
} |
deba@1833 | 43 |
sort(data.begin(), data.end()); |
deba@1833 | 44 |
} |
deba@1833 | 45 |
|
deba@1833 | 46 |
void testStableSort() { |
deba@1833 | 47 |
int n = 10000000; |
deba@1833 | 48 |
vector<int> data(n); |
deba@1833 | 49 |
for (int i = 0; i < n; ++i) { |
deba@1833 | 50 |
data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500; |
deba@1833 | 51 |
} |
deba@1833 | 52 |
stable_sort(data.begin(), data.end()); |
deba@1833 | 53 |
} |
deba@1833 | 54 |
|
deba@1833 | 55 |
void testSorts() { |
deba@1833 | 56 |
{ |
deba@1833 | 57 |
int n = 10000000; |
deba@1833 | 58 |
vector<int> data(n); |
deba@1833 | 59 |
} |
deba@1833 | 60 |
cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl; |
deba@1833 | 61 |
cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl; |
deba@1833 | 62 |
cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl; |
deba@1833 | 63 |
cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl; |
deba@1833 | 64 |
} |
deba@1833 | 65 |
|
deba@1833 | 66 |
|
deba@1833 | 67 |
int main() { |
deba@1833 | 68 |
testSorts(); |
deba@1833 | 69 |
return 0; |
deba@1833 | 70 |
} |