4

Is there a readily available equivalent to numpy.partition in JavaScript, via a library or built in?

It does not seem like any of the popular relevant libraries such as underscore.js provide such a function. I am asking because I would like to be able to find the n highest (or lowest) elements in an array for the general case, without having to implement quickselect or introselect myself.

Partitioning an array at index n rearranges the array so that the element at n is in sorted order, and all the elements with index greater than n are larger than that element at n. Alternatively, the elements at indices less than n can all be less than the element at n. Either way, it is a partial sort that guarantees the position of a particular element and the distribution of the elements above and below it.

A full sort satisfies the same conditions of course, but runs in O(n log n) time, while partitioning generally runs in O(n) time (average case for quickselect, worst case for introselect).

The jQuery plugin QuickSelect does something completely different, despite the promising name.

Part of the motivation for this question: Possible to use Math.min to get second smallest number from array?

oguz ismail
  • 1
  • 16
  • 47
  • 69
Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
  • You might want to explain what partition does for benefit of javascript experts who don't use numpy. I haven't used it much but my impression is that it is an incomplete sort. The theory​ is probably well known, but I haven't seen it in other languages. – hpaulj Nov 16 '17 at 17:10
  • @hpaulj. More than "I would like to be able to find the n highest (or lowest) elements in an array for the general case"? – Mad Physicist Nov 16 '17 at 17:11
  • This question is [off-topic (#4)](/help/on-topic) and should be closed as such. – zzzzBov Nov 16 '17 at 18:07
  • @zzzzBov I would be happy to ask this elsewhere if you could recommend an appropriate forum. – Mad Physicist Nov 16 '17 at 18:58
  • @MadPhysicist might get a reasonable response on chat or at least a discussion of where to look. SO doesn't really have a great solution for "(what|which) (plugin|library|framework) should I use for [problem]?" style questions. They tend to rely too much on opinions and often just get punted offsite. – zzzzBov Nov 16 '17 at 19:32
  • @zzzzBov. I am not asking for an opinion here. Any implementation of the desired operation if fine. That being said, I don't have a problem being punted off site. I would be glad to punt myself if I knew which site this sort of question *would* be on topic for. – Mad Physicist Nov 16 '17 at 19:37
  • @zzzzBov. Where do you recommed I ask on chat? I have never used chat except when comment threads get too long. – Mad Physicist Nov 16 '17 at 19:40
  • I feel that @zzzzBov is being pedantic about the rules. Perhaps if you rephrased the question as how to implement the method in javascript, rather than asking which library has already implemented it? – binarymax Nov 16 '17 at 19:43
  • @MadPhysicist, I'm not trying to be rude here, but i'm not interested in training you on how to search or ask for help on the internet. I also made no claims that you were asking for an opinion. Please take some time to review the link I sent previously because the point is that there isn't a stack exchange site that I know of where this sort of question is encouraged. Meta has good information about how to use chat. To be clear, I think you've written your question quite well and I hope you can find a good answer to it. – zzzzBov Nov 16 '17 at 19:45
  • @binarymax certainly if the question were rephrased to ask for help implementing the algorithm it would be on topic, but that would also require showing an attempt and the question would need to be specifically about the parts where OP was struggling. The problem is then OP is reinventing the wheel, which is certainly wasteful if a library exists. – zzzzBov Nov 16 '17 at 19:47
  • @zzzzBov. Thanks. I was certainly not asking for how to search properly on the internet. I have done plenty of that. Unfortunately all my results were negative. Pointing me to meta to RTFM on chat is exactly what I was looking for. – Mad Physicist Nov 16 '17 at 19:47
  • @binarymax. I don't think I would need help implementing the algorithm myself in JavaScript. My implementation might not use all the latest and greatest frills but I am confident that I know introselect well enough to get it working. The whole point of the question is that it is not a trivial task to write properly and I was really hoping someone already did the work for me :) – Mad Physicist Nov 16 '17 at 19:49
  • I googled "quick select javascript" and the top result is this, which from the readme seems to be right: https://github.com/mourner/quickselect – c2huc2hu Nov 16 '17 at 20:09
  • @user3080953. Thanks. Apparently I do need a lesson in how to search the internet. If you put that into a one-line answer, I would be glad to accept it. – Mad Physicist Nov 16 '17 at 20:28

1 Answers1

1

Package to do quickselect.

Github

NPM

(I've never used this package, but from the README, it seems to be what OP is looking for)

c2huc2hu
  • 2,447
  • 17
  • 26