QuickSort on ranges

[Ali Çehreli]

On 9/12/20 11:25 AM, jerome wrote:

 > --------------------------------
 > import std.stdio : writeln;
 > import std.algorithm.sorting;
 >
 > pure void quickSort(T) (T[] r)
 > {
 >    if (r.length > 1)
 >    {
 >      size_t p = pivotPartition(r, r.length-1);  //r[$-1] is swapped 
to r[p]
 >
 >      quickSort( r[ 0..p ] );
 >      quickSort( r[ p+1..$ ] );
 >    }
 > }
 >
 > void main()
 > {
 >    int[] arr = [9,7, 4 , 8, 5, 3, 1];
 >    quickSort!(int)(arr);

   // No need to specify int there because it's deduced from
   // the parameter. Pretty cool: :)
   quickSort(arr);

 >    writeln("arr : ", arr );
 >
 > }
 > --------------------------------
 >
 > I spent some time understanding "ranges", but at the end I am surprised
 > I didn't use them. At the beginning I wrote something like quickSort(
 > Range r ) and tried randomaccessrange etc but I didn't manage to make it
 > work.

Agreed. The most common range type is InputRange and most algorithms 
don't require more than that. Combined with slices being the most common 
RandomAccessRange, it's not obvious why one needs to write algorithms 
that require RandomAccessRange.

So, your algorithm is very useful already but as you said, it can't work 
with all RandomAccessRanges:

   import std.range;
   auto arr2 = iota(5).array;
   quickSort(chain(arr, arr2));    // <-- Compilation error

chain() is a very smart algorithm that return a range type that can be a 
RandomAccessRange if all the ranges given to it are RandomAccessRanges. 
(Pretty awesome and very practical that we can write ranges like chain() 
in D!)

So, to make your algorithm with any RandomAccessRange, we need to change 
it like this:

pure void quickSort(R) (R r)    // <-- The only change

Now the quickSort(chain(arr, arr2)) expression can be compiled and the 
result is awesome too:

   // Wow! Your quickSort operated on the elements of two
   // separate ranges! :)
   writeln(arr);
   writeln(arr2);

Optionally, you can put a template constraint on your algorithm to 
communicate the fact that it can only work with RandomAccessRanges:

import std.range : isRandomAccessRange;

pure void quickSort(R) (R r)
if (isRandomAccessRange!R)    // <-- Here
{
   // ...
}

Doing that moves potential compilation errors from your algorithm to the 
caller. For example, if they call your algorithm with int[string], they 
will get a compilation error saying "you can't call this function with 
int[string]".

Ali