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
