alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
deba@1833: #define NDEBUG
deba@1833: 
deba@1833: #include <lemon/time_measure.h>
deba@1833: #include <lemon/smart_graph.h>
deba@1833: #include <lemon/graph_utils.h>
deba@1833: #include <lemon/maps.h>
deba@1833: #include <lemon/error.h>
deba@1833: 
deba@1833: #include <lemon/radix_sort.h>
deba@1833: 
deba@2242: #include <lemon/random.h>
deba@2242: 
deba@1833: #include <vector>
deba@1833: #include <algorithm>
deba@1833: #include <cmath>
deba@1833: 
deba@1833: using namespace std;
deba@1833: using namespace lemon;
deba@1833: 
deba@1833: void testRadixSort() {
deba@1833:   int n = 10000000;
deba@1833:   vector<int> data(n);
deba@1833:   for (int i = 0; i < n; ++i) {
deba@2242:     data[i] = rnd[1000] - 500;
deba@1833:   }
deba@1833:   radixSort(data.begin(), data.end());
deba@1833: }
deba@1833: 
deba@1833: 
deba@1833: void testCounterSort() {
deba@1833:   int n = 10000000;
deba@1833:   vector<int> data(n);
deba@1833:   for (int i = 0; i < n; ++i) {
deba@2242:     data[i] = rnd[1000] - 500;
deba@1833:   }
deba@1833:   counterSort(data.begin(), data.end());
deba@1833: }
deba@1833: 
deba@1833: void testSort() {
deba@1833:   int n = 10000000;
deba@1833:   vector<int> data(n);
deba@1833:   for (int i = 0; i < n; ++i) {
deba@2242:     data[i] = rnd[1000] - 500;
deba@1833:   }
deba@1833:   sort(data.begin(), data.end());
deba@1833: }
deba@1833: 
deba@1833: void testStableSort() {
deba@1833:   int n = 10000000;
deba@1833:   vector<int> data(n);
deba@1833:   for (int i = 0; i < n; ++i) {
deba@2242:     data[i] = rnd[1000] - 500;
deba@1833:   }
deba@1833:   stable_sort(data.begin(), data.end());
deba@1833: }
deba@1833: 
deba@1833: void testSorts() {
deba@1833:   {
deba@1833:     int n = 10000000;
deba@1833:     vector<int> data(n);
deba@1833:   }
deba@1833:   cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl;
deba@1833:   cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl;
deba@1833:   cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl;
deba@1833:   cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl;
deba@1833: }
deba@1833: 
deba@1833: 
deba@1833: int main() {
deba@1833:   testSorts();
deba@1833:   return 0;
deba@1833: }