template < typename T >
void
__PartitionStep(std::vector < T >& vec, long& i, long& j, long& q, long& r, T& pivot, int& c)
{
j = r;
pivot = vec[r];
i = q-1;
while (i < j)
{
while (c*vec[++i] <=
c*pivot && i < j);
while (c*vec[--j] >=
c*pivot && i < j);
if(i < j)
std::swap(vec[i], vec[j]);
}
std::swap(vec[i], vec[r]);
}
template < typename T >
void __QuickSortRecursive(std::vector < T >&
vec, long q, long r, int& c)
{
if (r - q <
LENGTH_MIN)
{
InsertSort(vec, q, r, c == 1 ? true : false);
return;
}
T pivot;
long i, j;
__PartitionStep(vec, i, j, q, r, pivot, c);
__QuickSortRecursive(vec, q, i-1, c);
__QuickSortRecursive(vec, i+1, r, c);
}
template < typename T >
void __QuickSortParallelRecursive(std::vector < T >
&vec, long q,
long r, int &numBusyThreads, const int numThreads, int& c)
{
if (r - q <
LENGTH_CRTL)
{
__QuickSortRecursive(vec, q, r, c);
return;
}
T pivot;
long i, j;
__PartitionStep(vec, i, j, q, r, pivot, c);
if (numBusyThreads
>= numThreads)
{
if(i-q <
LENGTH_CRTL)
{
__QuickSortRecursive(vec, q, i-1, c);
__QuickSortParallelRecursive(vec, i+1, r, numBusyThreads, numThreads, c);
}
else if(r-i < LENGTH_CRTL)
{
__QuickSortRecursive(vec, i+1, r, c);
__QuickSortParallelRecursive(vec, q, i-1, numBusyThreads, numThreads, c);
}
else
{
__QuickSortParallelRecursive(vec, q, i-1, numBusyThreads, numThreads, c);
__QuickSortParallelRecursive(vec, i+1, r, numBusyThreads, numThreads, c);
}
}
else
{
#pragma omp atomic
numBusyThreads += 2;
#pragma omp parallel
shared(vec,numBusyThreads)
{
#pragma omp sections
nowait
{
#pragma omp
section
{
__QuickSortParallelRecursive(vec, q, i-1, numBusyThreads, numThreads, c);
#pragma omp atomic
--numBusyThreads;
}
#pragma omp
section
{
__QuickSortParallelRecursive(vec, i+1, r, numBusyThreads, numThreads, c);
#pragma omp atomic
--numBusyThreads;
}
}
}
}
}
