Discussion on: Haskell Quicksort in JavaScript

[Darryl Noakes]

Just a question, I may be missing something.

You said

Then we use the ternary operator to return an empty array if the head is undefined.

Yet your code is:

x !== undefined 
  ? [] 
  : [
    ...
  ]

This will return an empty array when x is not undefined, and do more sorting if it is undefined.

Indeed, I ran the following code, and it logged [].

const qs = ([x, ...xs]) => x !== undefined 
  ? [] 
  : [
    ...qs(xs.filter(s => s <= x)),
    x,
    ...qs(xs.filter(b => b > x))
  ]

let arr = [5, 3, 1, 8, 6, 0, 2, 4, 7, 9];

console.log(qs(arr));

To fix, simply change the !== undefined to === undefined.
You could also swap the clauses in the ternary expression instead.

I tested this and it works.
That will filter out any undefineds, or return an empty array if the first element is undefined.
null gets sorted to the the beginning of the array.

[Caleb Weeks]

Thanks for the catch! I'll update!

[Darryl Noakes]

Update:

I played around with it and came up with this:

let qs = (xs) => (
  xs.length > 0
    ? xs[0] !== undefined
      ? [
          ...qs(xs.slice(1).filter(s => s <= xs[0])),
          xs[0],
          ...qs(xs.slice(1).filter(b => b > xs[0]))
        ]
      : qs(xs.slice(1))
    : []
)

This allows for having undefined at the beginning of the array. Not as elegant, but required due to x being undefined if an empty array is passed in (which is when the quicksort recursion ends and starts "undoing").

I did a few runs in JSBen.ch using my Pi 4 4GB.

• native: (23981) 100%
• orig: (15948) 66.5%
• this: (14596) 60.86%

JSBen.ch test.

JSBench.me was less favorable.
I get this:

• orig ~6000 - ~9500 ops/s; ~60% - ~85% slower
• this: ~3000 - ~5000 ops/s; ~75% - ~95% slower
• native: ~24000 ops/s

JSBench.me test

Note: see updated benchmark code in my later comments.

[Sebastian Frey]

Or use nested ternary operators:

const qs = ([x, ...xs]) => x === undefined 
  ? xs.length === 0
  ? []
  : qs(xs)
  : [
    ...qs(xs.filter(s => s <= x)),
    x,
    ...qs(xs.filter(b => b > x))
  ]

let arr = [5, 3, 1, 8, 6, 0, 2, 4, 7, 9];

console.log(qs(arr));

[Darryl Noakes]

I tried to figure out something like that, but got stuck.
Much better, thanks!

(Now to rerun the benchmarks...)

[Darryl Noakes]

New benchmark results:

Run 1:

• native (23740) 100%
• orig quicksort (15751) 66.35%
• undefined-safe quicksort (15673) 66.02%

Run 2:

• native (24123) 100%
• orig quicksort (15903) 65.92%
• undefined-safe quicksort (15776) 65.4%

New JSBen.ch test

P.S. I dunno why I have got so stuck into this benchmarking :).

[Caleb Weeks]

Cool! Thanks for adding those benchmarks! I wonder how it compares to this version:

const qs = (arr) => [...arr].sort((a, b) => a - b);

[Darryl Noakes]

I did it with just .sort() (labeled as native), but I'm not sure how that compares.
It does affect the sort order though: plain .sort() orders it [numbers, nulls, undefineds], while this orders it like the other implementations, with undefineds being put at the end instead of being filtered, i.e. [nulls, numbers, undefineds].

Feel free to write some more benchmarks yourself, if you want :).

I did those on my Pi 4 4GB, which is slowish.
It gets 24k ops/s for native sort while my phone (Galaxy A51 4GB) gets 30k ops/s.

[Darryl Noakes]

Update
I remembered something "quirky" about JavaScript's default sorting algorithm: it coerces values to strings and sorts them lexicographically.
The reason the plain sort worked was because all then numbers had the same number of digits. If they had varying numbers, it would have sorted them like this: [2, 20, 3, 30].

I have made updated JSBen.ch benchmarks using arr.sort((a, b) => a - b) (I can't manage to login to JSBench.me):

• JSBen.ch 1
• JSBen.ch 2