www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - QuickSort on ranges

reply jerome <jegaultier gmail.com> writes:
Hi fellow coders, I spent a couple of hours to implement a 
working, basic, quicksort. Practicing D. It finally boils down to 
that (intent to use the std, not to rewrite swap, etc):

--------------------------------
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);
   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.

My question is, is there a way to write this with "ranges" as the 
argument, or does this concept of slices with the [] notation 
takes precedence somehow on the concept of ranges, in this 
particular case?

2) how would YOU write it? Using std or not.

3) any comment/code correction welcome, I am learning :)

cheers
J
Sep 12 2020
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Sep 12 2020
parent reply jerome <jegaultier gmail.com> writes:
Thanks you very much Ali,

I will try to wrap my head around your inputs, and get a better 
understanding of ranges in the process. I feel there is a lot of 
power in D ranges, and like the hammer of Thor, I am not worthy 
yet :)
Oct 04 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/4/20 6:50 AM, jerome wrote:

 Thanks you very much Ali,
 
 I will try to wrap my head around your inputs, and get a better 
 understanding of ranges in the process. I feel there is a lot of power 
 in D ranges, and like the hammer of Thor, I am not worthy yet :)
 


Just to elaborate a bit further: Templates work by pattern matching. 
When you say

quickSort(T)(T[] r)

You are saying, match the parameter T[] to what is passed, and if it's a 
match, set T to the part of the parameter that matches. Therefore:

int[] => T = int
ubyte[] => T = ubyte

But if you leave off the array brackets:

quickSort(T)(T r)

Now T matches *any type* that you pass in, including ranges. Most range 
functions use templates because there is no supertype for ranges. They 
are checked by trying to compile the range primitives on them.

How you do more advanced checks other than pattern matching, is to use a 
template constraint, as Ali suggests.

In fact, since you are just using std.algorithm.pivotPartition, you can 
just look at the constraints it uses:

if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && 
hasAssignableElements!Range)

-Steve
Oct 04 2020
parent jerome <jegaultier gmail.com> writes:
I posted some sum-up on my github.

https://preview.tinyurl.com/y6sprdbq
Oct 18 2020