quickSort

[Jonathan M Davis]

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