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

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

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 :)

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

I posted some sum-up on my github.

https://preview.tinyurl.com/y6sprdbq