On Wednesday, September 14, 2011 01:34:34 hdsh wrote:
> this my try
>
> int[] quickSort(int[] arr) {
> int[] result = quickSort(filter!(arr < arr[0])(arr)) ~ arr[0] ~
> quickSort(filter!(arr > arr[0])(arr));
> }
>
> but it fail to compile
filter does not return an array. It returns a new range which wraps the
original array. As you iterate over the range, it skips elements which don't
match the predicate. If you want to make an array out of it, you use
std.array.array, but that allocates a new array. But as filter doesn't return
int[], you can't pass its result to your quickSort function, nor can you
concatenate it (if you want to concatenate ranges, you use std.range.chain,
which chains them together without allocating anything - it just goes to each
successive range when iterating over it). Normally, range-based functions are
templated so that they can deal with a variety of range types.
If all you're looking for is a sort function, then you can use
std.algorithm.sort, but if you're just trying to implement quick sort in D,
because you want to implement it in D, then you're going to have to rework how
your algorithm works. Either, you're going to have to templatize it (and use
chain), use array (which would be less than efficient), or you're going to have
to use something other than filter.
Personally, I'd advise reworking it so that it doesn't use filter if you want
it to be efficient. Using std.array.array would work but would be inefficient,
whereas templatizing quickSort might run into trouble. I'm not sure whether
such a recursive templated function would work or not. It would depend on
whether each call to filter required a new template instantiation or not.
In any case, your core problem here is the fact that filter does not return
int[]. It returns a new range type.
- Jonathan M Davis
