Ranges help

Dmitry Olshansky dmitry.olsh at gmail.com
Wed Oct 12 13:04:51 PDT 2011


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


More information about the Digitalmars-d-learn mailing list