Re: quickSort

[Timon Gehr]

On 09/14/2011 03:34 AM, 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

Note that this approach is an inefficient way of implementing a sorting 
routine.

This works:

int[] quickSort(int[] arr) {
    if(!arr.length) return [];
    return quickSort(array(filter!((a){return a < arr[0];})(arr))) ~ 
arr[0] ~
        quickSort(array(filter!((a){return a > arr[0];})(arr)));
}

I'll go quickly through how I fixed it:


int[] quickSort(int[] arr) {
    if(!arr.length) return []; // base case for recursion
    return // return statement for giving back a result
    quickSort(array( // turn the lazy filter range into an array
    filter!(
        (a){return a < arr[0];} // delegate literal passed to filter
    )(arr))) ~ arr[0] ~
    quickSort(array(filter!(
        (a){return a >= arr[0];} //allow multiple elements that are 
equal to the pivot element
    )(arr[1..$]))); // only include the pivot once
}


If you have particular questions about this solution, feel free to ask.