Bitonic sort(也称双调排序)

Bitonic sequence. A sequence (a_{{1}}, a_{{2}},..., a_{{m}} ) is said to be bitonic if and only if:
(a) Either there is an integer j, 1 ≤ j ≤ 2m, such that a_{{1}} leq   a_{{2}}leq ... a_{{j}}geq  a_{{j+1}}geq  a_{{j+2}}geq ...geq  a_{{m}}
(b) Or the sequence does not initially satisfy the condition in (a), but can be shifted cyclically until the condition is satisfied.

/*
 * binotic.h
 *
 *  Created on: 2015年5月17日
 *      Author: zhangjun
 */
#ifndef BITONIC_SORT_H_
#define BITONIC_SORT_H_
#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;
class bitonic_sorter
{
public:
	bitonic_sorter(int a[], int len);
	void sort(bool direction = true);
	void sort_for_arbitary_length(bool direction = true);
private:
	int *array;
	int length;
	void bitonic_sort(int low, int len, bool direction);
	void bitonic_sort_for_arbitary_length(int low, int len, bool direction);
	void bitonic_merge(int low, int len, bool direction);
	void bitonic_merge_for_arbitary_length(int low, int len, bool direction);
	void compare_and_swap(int i, int j, bool direction);
	int greatest_power_of_2_lessthan(int len);
};
#endif /* BINOTIC_H_ */

 

/*
 * bitonic_sort.cpp
 *
 *  Created on: 2015年5月17日
 *      Author: zhangjun
 */
#include "bitonic_sort.h"
bitonic_sorter::bitonic_sorter(int a[], int len)
{
	array = a;
	length = len;
}
void bitonic_sorter::sort(bool direction)
{
	bitonic_sort(0, length, direction);
}
void bitonic_sorter::sort_for_arbitary_length(bool direction)
{
	bitonic_sort_for_arbitary_length(0, length, direction);
}
void bitonic_sorter::bitonic_sort(int low, int len, bool direction)                   // bitonic_sort
{
	if(len > 1)
	{
		int m = len/2;
		bitonic_sort(low, m, direction);
		bitonic_sort(low+m, m, !direction);
		bitonic_merge(low, len, direction);
	}
}
void bitonic_sorter::bitonic_sort_for_arbitary_length(int low, int len, bool direction)               // bitonic_sort_for_arbitary
{
	if(len > 1)
	{
		int m = len/2;
		if(direction == true)
		{
			bitonic_sort_for_arbitary_length(low, m, !direction);                                                                   // len-m > m
			bitonic_sort_for_arbitary_length(low+m, len-m, direction);                                                       // the big end
			bitonic_merge_for_arbitary_length(low, len, direction);
		}
		else
		{
			int half = greatest_power_of_2_lessthan(len);
			bitonic_sort_for_arbitary_length(low, len-half, !direction);                                                        // half > hen -half
			bitonic_sort(low+len-half, half, direction);                                                // the big end
			bitonic_merge_for_arbitary_length(low, len, direction);
		}
	}
}
void bitonic_sorter::bitonic_merge(int low, int len, bool direction)
{
	if(len > 1)
	{
		int m = len/2;
		for( int i = low; i < low + m; i++)
			compare_and_swap(i, i+m, direction);
		bitonic_merge(low, m, direction);
		bitonic_merge(low+m, m, direction);
	}
}
void bitonic_sorter::bitonic_merge_for_arbitary_length(int low, int len, bool direction)
{
	if(len > 1)
	{
		int m = greatest_power_of_2_lessthan(len);                                             // low+m >= low+len-m
		for( int i = low; i < low + len - m; i++)
			compare_and_swap(i, i+m, direction);
		bitonic_merge(low, m, direction);                                                                   // m >= len -m
		bitonic_merge(low+m, len-m, direction);
	}
}
void bitonic_sorter::compare_and_swap(int i, int j, bool direction)
{
	if(direction ==(array[i]>array[j]))
		std::swap(array[i], array[j]);
}
int bitonic_sorter::greatest_power_of_2_lessthan(int len)
{
	int p = 1;
	while(p<len)
		p = p<<1;
	return p>>1;
}

 

/*
 * test.cpp
 *
 *  Created on: 2015年5月6日
 *      Author: zhangjun
 */
#include<stdio.h>
#include<string.h>
#include"bitonic_sort.h"
int main()
{
	int num1[8] = {3, 67, 3, 5, 8, 4, 7, 9};
	int num2[34] = {7, 5, 8, 3, 5, 78, 9, 5, 6, 23,24,1,8,10,32, 2, 3, 8, 9, 21, 15, 3, 4, 8, 9, 6, 3, 2, 1,78,43, 56, 23, 41};
	bitonic_sorter s1(num1, 8);
	bitonic_sorter s2(num2, 34);
	s1.sort(false);
	std::copy(num1, num1+8, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	s2.sort_for_arbitary_length(true);
	std::copy(num2, num2+34, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	return 0;
}
/*
 * test.cpp
 *
 *  Created on: 2015年5月6日
 *      Author: zhangjun
 */
#include<stdio.h>
#include<string.h>
#include"bitonic_sort.h"
int main()
{
	int num1[8] = {3, 67, 3, 5, 8, 4, 7, 9};
	int num2[34] = {7, 5, 8, 3, 5, 78, 9, 5, 6, 23,24,1,8,10,32, 2, 3, 8, 9, 21, 15, 3, 4, 8, 9, 6, 3, 2, 1,78,43, 56, 23, 41};
	bitonic_sorter s1(num1, 8);
	bitonic_sorter s2(num2, 34);
	s1.sort(false);
	std::copy(num1, num1+8, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	s2.sort_for_arbitary_length(true);
	std::copy(num2, num2+34, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	return 0;
}

 
cuda bitonic代码

__global__ static void bitonicSort(int * values)
{
    extern __shared__ int shared[];
    const int tid = threadIdx.x;
    // Copy input to shared mem.
    shared[tid] = values[tid];
    __syncthreads();
    // Parallel bitonic sort.
    for (int k = 2; k <= NUM; k *= 2)                   // from 2 to
    {
        // Bitonic merge:
        for (int j = k / 2; j>0; j /= 2)                // from k/2 to 1
        {
            int ixj = tid ^ j;
            if (ixj > tid)           // tid 对应位为0, ixj对应位为1
            {
                if ((tid & k) == 0)               // 对应位为0,ascending
                {
                    if (shared[tid] > shared[ixj])
                    {
                        swap(shared[tid], shared[ixj]);
                    }
                }
                else                             // 对应位为1,descending
                {
                    if (shared[tid] < shared[ixj])
                    {
                        swap(shared[tid], shared[ixj]);
                    }
                }
            }
            __syncthreads();
        }
    }
    // Write result.
    values[tid] = shared[tid];
}

 
 

Leave a Reply

Your email address will not be published. Required fields are marked *