xqsort.h

归并排序的并行算法 intel 多线程优化大赛

/*/////////////////////////////////////////
// 版权所有(C)  2000-2008 邓辉           //
// Email：      [e-mail]  //
// 说明：       Intel线程优化大赛参赛作品//
/////////////////////////////////////////*/

#ifndef XQSORT_HEAD
#define XQSORT_HEAD

#include "XSortPub.h"
#include <deque>
using namespace std;

#define XQSORT_CUTOFF 40

// 查找中值
template<class Type>
__inline void XMedian(Type* pBeg, Type* pMid, Type* pEnd)
{	
	if(*pBeg > *pMid) { const Type t = *pBeg; *pBeg = *pMid; *pMid = t;}
	if(*pMid > *pEnd) { const Type t = *pMid; *pMid = *pEnd; *pEnd = t;}
	if(*pMid > *pBeg) { const Type t = *pBeg; *pBeg = *pMid; *pMid = t;}
}

//插入排序
template<class Type>
__inline void XISort(Type* pBeg, Type* pEnd)
{
	Type *i,*j;

	if (pBeg != NULL && pEnd > pBeg) 
	{
		for (i = pBeg + 1; i < pEnd; ++i)
		{
			const Type t = *i;
			for (j = i; j > pBeg && *(j - 1) > t; --j) *j = *(j - 1);
			*j = t;
		}
	}
}

//快速排序函数
template<class Type>
__inline Type* XPartition(Type* pBeg, Type* pEnd)
{
	if (pEnd - pBeg - 1 <= XQSORT_CUTOFF)
	{	//数据较少时使用插入排序,减少堆栈深度
		XISort(pBeg, pEnd);
		return NULL;
	}
	else
	{	//快速排序,返回分割点
		Type *i = pBeg, *j = pEnd, *pMid = pBeg + ((pEnd - pBeg) >> 1);
		XMedian(pBeg, pMid, pEnd - 1);
		Type m = *pBeg;

		while ((++i) < pEnd  && *i <= m);
		while ((--j) > pBeg	 && *j > m);
		while (i < j) 
		{
			const Type t = *i; *i = *j; *j = t;
			do ++i; while (*i <= m);
			do --j; while (*j > m);
		}
		m = *pBeg; *pBeg = *j; *j = m;

		return j;
	}
};

//快速排序函数_非递归版本
template<class Type>
__inline void XPartitionStack(Type* pBeg, Type* pEnd)
{
	deque<Type*> xStack;

	xStack.push_back(pBeg);
	xStack.push_back(pBeg);

	while(xStack.size())
	{
		Type* pMid = XPartition(pBeg, pEnd);

		if (pMid == NULL)
		{
			pEnd = xStack.back(); xStack.pop_back();
			pBeg = xStack.back(); xStack.pop_back();
		}
		else
		{
			xStack.push_back(pMid + 1);
			xStack.push_back(pEnd);
			pEnd = pMid;
		}
	}
};

//快速排序Task
template<class Type>
class CXQSortTask: public tbb::task 
{
	Type	*m_pBeg,*m_pEnd;
	BOOL	m_bIsContinuation;
public:
	CXQSortTask( Type* pBeg, Type* pEnd) : m_pBeg(pBeg), m_pEnd(pEnd), m_bIsContinuation(FALSE) { }

	tbb::task* execute() 
	{
		tbb::task *pNextA = NULL, *pNextB = NULL;

		if(m_pEnd - m_pBeg < 1024 * 32)
		{
			//非递归快速排序
			XPartitionStack(m_pBeg, m_pEnd);
		}
		else
		{
			if( !m_bIsContinuation ) 
			{	//移动数据并得到分割点
				Type* pSplit = XPartition(m_pBeg, m_pEnd);

				if(pSplit != NULL)
				{   //分裂新的Task
					pNextA = new( allocate_child() ) CXQSortTask(m_pBeg,     pSplit);

					pNextB = new( allocate_child() ) CXQSortTask(pSplit + 1, m_pEnd);

					m_bIsContinuation = TRUE;

					recycle_as_continuation();

					set_ref_count(2);

					spawn(*pNextB);
				}
			} 
		}
		return pNextA;
	}
};

//快速排序_串行版本_递归函数
template<class Type>
void XQSortSerial_In(Type* pBeg, Type* pEnd) 
{
	Type* pSplit = XPartition<Type>(pBeg, pEnd);
	if(pSplit != NULL)
	{
		XQSortSerial_In(pBeg,       pSplit);
		XQSortSerial_In(pSplit + 1, pEnd);
	}
}

//快速排序_串行版本
template<class Type>
void XQSortSerial(Type* pSrc, uint32 nSize) 
{
	XQSortSerial_In(pSrc, pSrc + nSize);
}

//快速排序_并行版本
template<class Type>
void XQSortParallel(Type* pSrc, uint32 nSize) 
{
	CXQSortTask<Type>& xtask = *new(tbb::task::allocate_root()) CXQSortTask<Type>(pSrc, pSrc + nSize);
	tbb::task::spawn_root_and_wait(xtask);
}


#endif