双调排序

#include <ctime>
#include <unistd.h>
#include "omp.h"
#include "sys/sysinfo.h"
using namespace std;

long long arrayLength;
int * nums;
int coreNum = get_nprocs();



//core
void (int i, int groupLength) {
    int groupNum, flip, begin, delta;
    groupNum = (int)arrayLength / groupLength, flip = (groupLength == i ? 1 : -1);
    for (int group = 0; group < groupNum; group++) {
        begin = group * groupLength;

        if (flip == 1)
            delta = groupLength - 1;
        else
            delta = groupLength / 2;

        for (int k = 0; k < groupLength / 2; k++)
            if (nums[begin + k] > nums[begin + delta - flip * k])
                swap(nums[begin + k], nums[begin + delta - flip * k]);
    }
}


void bitonicSort() {
    for (int i = 2; i <= arrayLength; i <<= 1) {
        for (int j = i; j > 1; j >>= 1) {
//            omp_set_num_threads(coreNum);
//#pragma omp parallel
//            {
                halfCleaner(i, j);
//            };
        }
    }

}


//test
void init() {
    nums = new int[arrayLength];
    srand((unsigned) time(nullptr));
    for (int i=0;i<arrayLength;++i)
        nums[i] = rand() % 100 + 1;
}


void drop(){
    delete []nums;
}


bool judge() {
    for (int i = 1; i < arrayLength; ++i)
        if (nums[i - 1] > nums[i])
            return false;
    return true;
}


//demo
int main(int argc, const char *argv[]) {
    if (argc != 2) {
        cout << "usage: bitonicSort bitNum" << endl;
        return 0;
    }
    else
        arrayLength = 1 << atoi(argv[1]);
    
    init();
    
    clock_t start = clock();
    bitonicSort();
    cerr << "time: " << (double)(clock() - start)/CLOCKS_PER_SEC << "s." << endl;
    
    if (judge())
        cerr << "Accept" << endl;
    else
        cerr << "Wrong Answer" << endl;

    drop();

    return 0;
}