quickSort

[Timon Gehr]

On 09/14/2011 04:12 AM, Timon Gehr wrote:
> 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)));
> }


Sry, accidentally sent a first draft. This is how it should have looked.

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[1..$])));
}



>
> 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.
>
>