-
-
Save kangax/6c4407941d976fe00948 to your computer and use it in GitHub Desktop.
quicksort :: (Ord a) => [a] -> [a] | |
quicksort [] = [] | |
quicksort (x:xs) = | |
let smallerSorted = quicksort (filter (<=x) xs) | |
biggerSorted = quicksort (filter (>x) xs) | |
in smallerSorted ++ [x] ++ biggerSorted |
/* | |
1) passing array | |
> quicksort([4,3,2,1]); // => [1,2,3,4] | |
*/ | |
function quicksort(tail) { | |
if (tail.length === 0) return []; | |
let head = tail.splice(0, 1)[0]; | |
return quicksort(tail.filter( _ => _ <= head)) | |
.concat([head]) | |
.concat(quicksort(tail.filter( _ => _ > head ))) | |
} | |
/* | |
2) via arguments | |
> quicksort(4,3,2,1); // => [1,2,3,4] | |
or: | |
> quicksort(...[4,3,2,1]); // => [1,2,3,4] | |
*/ | |
function quicksort(x, ...xs) { | |
if (arguments.length === 0) return []; | |
return quicksort(...xs.filter( _ => _ <= x)) | |
.concat([x]) | |
.concat(quicksort(...xs.filter( _ => _ > x ))) | |
} |
Yeah, why the hell would you waste your time typing out "array.sort((a, b) => a - b);" only to get back 25,384x the run speed? Seriously, cute but useless.
Here is mine:
const qsort = ([pivot, ...tail]) =>
tail.length ?
[...qsort(tail.filter(x=>x<pivot)),
pivot,
...qsort(tail.filter(x=>x>=pivot))]
: !isNaN(pivot) ?
[pivot]
:
[]
I don't know how I should feel about this one, but I like the fact that you can almost read it like "pattern matching".
And for anyone wondering: yes, using the spread operator results in a performance drop.
[...Array(100000)].map(Math.random).sort((a, b) => a-b)
runs in 127ms.
qsort([...Array(100000)].map(Math.random))
runs in 479ms.
Using concat
instead of [...before, pivot, ...after] brings it down to 367ms.
And, finally, using
const qsortnd = array => {
const head = array[0], tail = array.slice(1)
return array.length ?
qsortnd(tail.filter(x=>x<array[0]))
.concat(head)
.concat(qsortnd(tail.filter(x=>x>=array[0])))
:
[]
}
instead makes it run in 275ms.
In your qsort
"pattern matching" lookalike -
const qsort = ([pivot, ...tail]) =>
tail.length
? // then ...
: // else..
You could use default arguments to your advantage -
const None =
Symbol ()
const qsort = ([ pivot = None, ...tail ]) =>
pivot === None
? // then ...
: // else ...
In qsortnd
, you call tail.filter
twice per element in the array resulting in many wasted cycles. Using reduce
we can collapse the two loops into just one -
const append = (x, xs = []) =>
xs .concat ([ x ])
const partition = (p, xs = []) =>
xs .reduce
( ([ t, f ], x) =>
p (x)
? [ append (x, t), f ]
: [ t, append (x, f) ]
, [ [], [] ]
)
const [ left, right ] =
partition
( x => x < 3
, [ 6, 2, 1, 4, 5, 3 ]
)
console .log (left, right)
// [ 2, 1 ]
// [ 6, 4, 5, 3 ]
Both qsort
and qsortnd
can overflow the stack for large arrays. Can you think of a way around this? (Hint: it can still be recursive! and fast!)
I like this one :)
const quicksort = array => { if (array.length === 0) return []; let [x, ...xs] = array; return [ ...quicksort(xs.filter(y => y < x)), x, ...quicksort(xs.filter(y => y >= x)) ]; };
One issue is performance since you are filtering the same array twice
function quickSort(values = []) {
const [pivot, ...restValues] = values;
if (!pivot) return [];
if (!restValues.length) return [pivot];
const [lesser, greater] = restValues.reduce((partitions, val) => {
partitions[+(val > pivot)].push(val);
return partitions;
}, [[], []]);
return [
...quickSort(lesser),
pivot,
...quickSort(greater),
];
}
So concise and beautiful!