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.
