N
OK, wenn wir alle so schön am posten sin...:
template<class Iter,class Ftor,class Ftor2>
void recursive_quicksort(Iter begin,Iter end,Ftor f,Ftor2 p)
{
if((end-begin)<2)
return;
Iter i=p(begin,end,f);
recursive_quicksort(begin,i,f,p);
recursive_quicksort(i+1,end,f,p);
};
template<class Iter,class Ftor,class Ftor2>
void iterative_quicksort(Iter begin,Iter end,Ftor f,Ftor2 p)
{
std::stack<Iter> s;
s.push(end);
s.push(begin);
Iter l;
Iter r;
Iter i;
while(!s.empty())
{
l=s.top();
s.pop();
r=s.top();
s.pop();
if((r-l)<2);
continue;
i=p(l,r,f);
s.push(i);
s.push(l);
s.push(r);
s.push(i+1);
};
};
/edit: partitionierungsfunktor:
template<class Iter,class Ftor>
struct std_partition
{
Iter operator()(Iter b,Iter e,Ftor f)
{
Iter i=b-1; //Suchzeiger
Iter j=e-1; //dito
typename std::iterator_traits<Iter>::value_type v=*(e-1);
for(;;)
{
while(++i!=e&&f(*i,v));
while(--j>i&&!f(*j,v));
if(i>=j)
break;
std::iter_swap(i,j);
};
std::iter_swap(i,e-1);
return i;
};
};
/edit:
recursive_quicksort braucht zum sortieren von 100000000 ints 4 Sekunden länger als std::sort - 24s.
/edit: mit cutoff für Kleine Daten:
template<class Iter,class Ftor,class Ftor2>
void recursive_quicksort_2_helper(Iter begin,Iter end,Ftor f,Ftor2 p,unsigned M)
{
if((end-begin)<M)
return;
Iter i=p(begin,end,f);
recursive_quicksort_2_helper(begin,i,f,p,M);
recursive_quicksort_2_helper(i+1,end,f,p,M);
};
template<class Iter,class Ftor,class Ftor2>
void recursive_quicksort_2(Iter begin,Iter end,Ftor f,Ftor2 p,unsigned M)
{
if(!((end-begin)<M))
{
Iter i=p(begin,end,f);
recursive_quicksort_2_helper(begin,i,f,p,M);
recursive_quicksort_2_helper(i+1,end,f,p,M);
};
insertionsort(begin,end,f);
};
mit M=9 - 25s
mit M=13 - 23s
mit M=15 - 24s
std::sort - 20
Da fällt mir ein, ich wollte schon vor längerer Zeit mal ein größeres benchmark machen...
