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.