双调排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#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;
}

https://blog.csdn.net/xbinworld/article/details/76408595

http://www.bryanlai.com/blog/%E5%8F%8C%E8%B0%83%E6%8E%92%E5%BA%8F%EF%BC%9A%E4%BB%8E%E4%B8%B2%E8%A1%8C%E5%88%B0%E5%B9%B6%E8%A1%8C%EF%BC%8C%E4%BB%A5%E5%8F%8Aopencl%E4%B8%8A%E7%9A%84%E5%AE%9E%E7%8E%B0-3/

https://blog.csdn.net/ljiabin/article/details/8630627