• Xinok (23/23) Oct 12 2011 This is in relation to my sorting algorithm. This is what I need to
• Dmitry Olshansky (43/66) Oct 12 2011 How about:
• Xinok (6/16) Oct 12 2011 Sorry, typo. That should be !isInfiniteRange. But I can drop
• travert phare.normalesup.org (Christophe) (6/37) Oct 14 2011 You should look at:
• Xinok (1/1) Oct 14 2011 Thanks. I'll run a benchmark with swapRanges, see how it compares to my ...

Xinok <xinok live.com> writes:

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();
}

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();
}


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

Dmitry Olshansky <dmitry.olsh gmail.com> writes:

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

Xinok <xinok live.com> writes:

On 10/12/2011 4:04 PM, Dmitry Olshansky wrote:
 On 12.10.2011 22:23, Xinok wrote:
 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

Sorry, typo. That should be !isInfiniteRange. But I can drop 
!isInfinteRange anyways, so:

isRandomAccessRange && isBidirectionalRange && hasSlicing

isRandomAccessRange can be a bidirectional range or an infinite forward 
range, so isBidirectionalRange is still required.

travert phare.normalesup.org (Christophe) writes:

Xinok , dans le message (digitalmars.D.learn:30054), a écrit :
 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();
 }
 
 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();
 }
 
 
 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


You should look at:
std.algorithm.SetUnion
std.algorithm.swapRanges

-- 
Christophe

Xinok <xinok live.com> writes:

Thanks. I'll run a benchmark with swapRanges, see how it compares to my own
code. But it would be better if I coded the merge function myself, since I can
do it in-place using very little memory.