I currently have a custom written Quicksort algorithm. But I thought I'd ask for someone to look over it, because there is at least one thing I am unsure of.
The code passes all the tests I have for it, but I cannot say if it's right or not.
The question is: which of these checks are required and which ones are not? I have commented out a great deal, and like I mentioned, it passes all my tests, but that doesn't mean it will always pass all tests, so...
Another thing is that I tried to parallellize the algorithm, but it turned out to be
slower. Not quite sure why. Perhaps someone has some suggestions or ideas...
Code:
template<template<typename> class PivotType, typename RandomIt>
void _Quicksort(RandomIt begin, RandomIt end, int Threads)
{
if (end - begin <= 1)
return;
RandomIt pivot = PivotType<RandomIt>::GetPivot(begin, end); // Gets the pivot
RandomIt left = begin, right = end - 2;
std::iter_swap(pivot, end - 1); // Swaps the two values pointed by the two iterators
pivot = end - 1;
//while (/*left <= right && *//*right >= begin && *//*left < end*/1)
for (;;)
{
while (*left < *pivot /*&& *//*left <= right && *//*left < end*/) ++left;
while (*right > *pivot /*&& right >= left && */&& right > begin) --right;
if (left > right) break;
std::iter_swap(left, right);
if (right == begin || left == end - 1) break;
/*if (left < end) */++left;
/*if (right > begin) */--right;
}
std::iter_swap(left, pivot);
//boost::thread* pThreads[2] = { NULL, NULL };
//if (Threads-- > 0)
//pThreads[0] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, begin, left, 0));
//else
Quicksort<PivotType>(begin, left);
//if (Threads-- > 0)
//pThreads[1] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, left + 1, end, 0));
//else
Quicksort<PivotType>(left + 1, end);
//if (pThreads[0]) pThreads[0]->join();
//if (pThreads[1]) pThreads[1]->join();
//Quicksort<PivotType>(begin, left);
//Quicksort<PivotType>(left + 1, end);
}