Implement Quicksort

[trevnorris]

Consider implementation of a quicksort. This would be especially useful once Typed Array Views and Buffers are supported.

[trevnorris]

Here's someone's implementation of quicksort: https://gist.github.com/4182296

Worth taking a look at.

[trevnorris]

not happening

[dotnetCarpenter]

You have your reasons for not wanting quicksort but I remembered a recursive quicksort function I made once, when I saw the one you linked to. Perhaps it can inspire for future use-cases.

var arr = [ 0.13837, 0.70843, 0.63302, 0.00802, 0.00141 ];
console.log(quicksort(arr)); //  [ 0.00141, 0.00802, 0.13837, 0.63302, 0.70843 ]

function quicksort(a) {
  if(a.length === 0) return []
  const x = a[0],
        xs = a.slice(1)
  let smallerSorted = quicksort( xs.filter(n => n<=x) ),
      biggerSorted = quicksort( xs.filter(n => n>x) )
  return smallerSorted.concat([x]).concat(biggerSorted)
}

[dotnetCarpenter]

Could also be written as this:

function quicksort(a) {
  'use strict'
  if(a.length === 0) return []
  const x = a[0]
  const xs = a.slice(1)
  const smallerSorted = quicksort( xs.filter(n => n<=x) )
  const biggerSorted = quicksort( xs.filter(n => n>x) )
  return smallerSorted.concat([x]).concat(biggerSorted)
}

the syntax highlighter does not like single const declaration 🐵

[dotnetCarpenter]

And as es5 for completeness:

function quicksort(a) {
  if (a.length === 0) return [];
  var x = a[0],
      xs = a.slice(1);
  var smallerSorted = quicksort(xs.filter(function (n) {
    return n <= x;
  })),
      biggerSorted = quicksort(xs.filter(function (n) {
    return n > x;
  }));
  return smallerSorted.concat([x]).concat(biggerSorted);
};

I'm learning haskell and kinda understand it better when I rewrite the functions in js. https://github.com/dotnetCarpenter/haskell1/tree/master/ch06

[trevnorris]

@dotnetCarpenter What I meant was that I don't have the time to implement it. If you'd like to submit a PR I'll be happy to review and land it.

[dotnetCarpenter]

This would be especially useful once Typed Array Views and Buffers are supported.

What does that mean? Do you have use case?

[trevnorris]

not sure. that comment has been lost to history.

[dotnetCarpenter]

@trevnorris I forgot about this one. Do you mind opening it and assign me if you can? Not sure that works when I'm not a Collaborator but I would like to create a PR when I have time and don't forget about this. I think the recursive function would need to be with proper tail call.. So need a little rewrite.

Unfortunately, I don't have time at the moment. But it's a fun little task.

[trevnorris]

@dotnetCarpenter Sent you an invite to be a collaborator. When you accept it you should be able to assign it to yourself.