OpenCL 双调排序 CPU 版

▶ 学习了双调排序，参考（https://blog.****.net/xbinworld/article/details/76408595）

● 使用 CPU 排序的代码

 #include <stdio.h>

 #define LENGTH 1024
 #define ASCENDING   1
 #define DESCENDING  0

 int a[LENGTH];

 void compare(int i, int j, int dir)
 {
     if (dir == (a[i]>a[j]))
     {
         int h = a[i];
         a[i] = a[j];
         a[j] = h;
     }
 }

 void bitonicMerge01(int lo, int cnt, int dir)// 先再大跨度（半区间长）上调整元素，再递归地在小跨度上进行相同的调整
 {
     if (cnt > )
     {
         int k = cnt / ;
         for (int i = lo; i < lo + k; i++)
             compare(i, i + k, dir);
         bitonicMerge01(lo, k, dir);
         bitonicMerge01(lo + k, k, dir);
     }
 }

 void bitonicSort01(int lo, int cnt, int dir)// 先递归地要求小跨度区间依次排成 “升↗降↘升↗降↘” 再在较大跨度上进行合并
 {
     if (cnt > )
     {
         int k = cnt / ;
         bitonicSort01(lo, k, ASCENDING);
         bitonicSort01(lo + k, k, DESCENDING);
         bitonicMerge01(lo, cnt, dir);
     }
 }

 void bitonicMerge02(int l, int r, const int dir)
 {
     if (r - l > )
     {
         int stride = (r - l) /  + ;
         for (int i = l; i < l + stride; i++)
             compare(i, i + stride, dir);
         bitonicMerge02(l, l + stride - , dir);
         bitonicMerge02(l + stride, r, dir);
     }
 }

 void bitonicSort02(int l, int r, const int dir)
 {
     if (r - l > )
     {
         int rNew = l + (r - l) / ;
         bitonicSort02(l, rNew, ASCENDING);
         bitonicSort02(rNew + , r, DESCENDING);
         bitonicMerge02(l, r, dir);
     }
 }

 void bitonicMerge03(int l, int r, const int dir)
 {
     if (r - l > )
     {
         int stride = (r - l) / ;
         for (int i = l; i < l + stride; i++)
             compare(i, i + stride, dir);
         bitonicMerge03(l, l + stride, dir);
         bitonicMerge03(l + stride, r, dir);
     }
 }

 void bitonicSort03(int l, int r, const int dir)
 {
     if (r - l > )
     {
         int rNew = l + (r - l) / ;
         bitonicSort03(l, rNew, ASCENDING);
         bitonicSort03(rNew, r, DESCENDING);
         bitonicMerge03(l, r, dir);
     }
 }

 int main()
 {
     int i, error;
     srand();
     for (i = ; i < LENGTH; a[i++] = rand());

     printf("\n");
     for (i = ; i < LENGTH; i++)
     {
         printf("%5d,", a[i]);
         if ((i + ) %  == )
             printf("\n");
     }

     //bitonicSort01(0, LENGTH, ASCENDING);        // 使用起点和长度
     //bitonicSort02(0, LENGTH - 1, ASCENDING);    // 使用左端点和右端点（都包含）
     bitonicSort03(, LENGTH, ASCENDING);          // 使用左端点和右端点（左包含右不包含）

     printf("\n");
     for (i = , error = -; i < LENGTH; i++)
     {
         printf("%5d,", a[i]);
         if (i < LENGTH -  && a[i] > a[i + ])
             error = i;
         if ((i + ) %  == )
             printf("\n");
     }
     if (error != -)
         printf("\n\nerror at i==%d, a[i]==%d, a[i+1]==%d", error, a[error], a[error + ]);

     getchar();
     return ;
 }

● 输出结果（临时改为排序 64 个元素，每行显示 16个）

  , ,,,,,,, ,,,,,,,,
,,, ,,, ,,,,,,,,,,
 ,,   ,,,,,,,, ,,,, ,,
,, ,,,,,,,,,,,,, ,

   ,  , , , , , , , , , ,,,,,,
,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,