On 12.10.2011 22:23, Xinok wrote:
This is in relation to my sorting algorithm. This is what I need to
accomplish with ranges in the most efficient way possible:
1. Merge sort - This involves copying elements to a temporary buffer,
which can simply be an array, then merging the two lists together. The
important thing is that it may merge left to right, or right to left,
which requires a bidirectional range.
c[] = a[0..$/2];
foreach(a; arr) if(!b.empty && !c.empty) if(b.front <= c.front){
a = b.front; b.popFront();
} else{
a = c.front; c.popFront();
}
How about:
if(b.empty)
copy(c, a);
else if(c.empty)
copy(b, a);
foreach(a; arr)
if(b.front <= c.front){
a = b.front;
b.popFront();
if(b.empty){
copy(c, a);
break;
}
}
else{
a = c.front; c.popFront();
if(c.empty){
copy(b, a);
break;
}
}
no need to check c if it hasn't changed from the last time, same about b.
2. Range swap - First, I need to do a binary search, which requires a
random access range. Then I need to swap two ranges of elements.
while(!a.empty && !b.empty){
swap(a.front, b.front);
a.popFront(); b.popFront();
}
If your ranges have equal lengths (or you assume it)
you can skip one of !a.empty or !b.empty in while clause.
Otherwise :
for(;;){
swap(a.front, b.front);
a.popFront();
if(a.empty)
break;
b.popFront();
if(b.empty)
break;
}
might save you a couple of ops in case a is shorter then b, and with
sorting every bit counts isn't it?
That's the best I can come up with. I'm wondering if there's a more
efficient way to accomplish what I have above.
I also need to figure out the template constraints. Would this be
correct? Or would this be too much?
isRandomAccessRange && !isFiniteRange && isBidirectionalRange && hasSlicing
isRandomAccessRange should be enough. Also why !isFinite how would one
sort infinite range? hasSlicing is needed though. So my take on this
would be:
isRandomAccessRange && hasSlicing
--
Dmitry Olshansky
