utestQuicksort.cpp 3.13 KB
Newer Older
1
// See LICENCE file at project root
2
#include "FUTester.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
3
#include "Utils/FQuickSort.hpp"
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <unistd.h>

/**
* This file is a unit test for the quick sort
*/


/** this class test the list container */
class TestQuickSort : public FUTester<TestQuickSort> {
    static bool IsSorted(long long array[], const long size){
        for(int idx = 1; idx < size ; ++idx){
            if(array[idx-1] > array[idx]){
                return false;
            }
        }
        return true;
    }

    void manyThreads(){
        const long Size = 100000;
        long long* const array = new long long[Size];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
26
        srand48(0);
27 28 29 30 31 32 33 34 35
        const int originalThreadsNumber = omp_get_num_threads();

        for(int idxThread = 1 ; idxThread <= omp_get_max_threads() ; idxThread *= 2){
            omp_set_num_threads(idxThread);

            for(long idx = 0 ; idx < Size ; ++idx){
                array[idx] = rand();
            }

36
            FQuickSort<long long, long>::QsOmp(array, Size);
37

38
            uassert(IsSorted(array,Size));
39 40 41 42 43 44 45
        }

        omp_set_num_threads(originalThreadsNumber);
        delete [] array;
    }

    void bigSize(){
46
        const long Size = 10000000;//100000000;
47 48 49 50 51 52
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = rand();
        }

53
        FQuickSort<long long, long>::QsOmp(array, Size);
54
        uassert(IsSorted(array,Size));
55 56 57 58

        delete [] array;
    }

59 60 61 62 63 64 65 66
    void reversed(){
        const long Size = 10000000;//100000000;
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = Size-idx;
        }

67
        FQuickSort<long long, long>::QsOmp(array, Size);
68 69 70 71 72 73 74 75 76 77 78 79 80
        uassert(IsSorted(array,Size));

        delete [] array;
    }

    void alreadySorted(){
        const long Size = 10000000;//100000000;
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = idx;
        }

81
        FQuickSort<long long, long>::QsOmp(array, Size);
82 83 84 85 86
        uassert(IsSorted(array,Size));

        delete [] array;
    }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
    void verySmallParts(){
        {
            long long values[2] = {0, 1};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 1);
        }
        {
            long long values[2] = {1, 0};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 1);
        }
        {
            long long values[2] = {0, 0};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 0);
        }
    }

108 109 110 111
    // set test
    void SetTests(){
        AddTest(&TestQuickSort::manyThreads,"Many threads");
        AddTest(&TestQuickSort::bigSize,"Big sort");
112 113
        AddTest(&TestQuickSort::reversed,"Reversed");
        AddTest(&TestQuickSort::alreadySorted,"Already Sorted");
BRAMAS Berenger's avatar
BRAMAS Berenger committed
114
        AddTest(&TestQuickSort::verySmallParts,"Small Parts");
115 116 117 118 119 120 121 122
    }
};

// You must do this
TestClass(TestQuickSort)