search

inspirit / jsfeat

JavaScript Computer Vision library.
MIT License
2.74k stars 372 forks source link

Have there been any benchmarks done on the sorting algorithm? #16

Closed arnorhs closed 11 years ago

arnorhs commented 11 years ago

The qsort algo in jsfeat.Math looks pretty similar to an introsort, but I haven't dived into it.

I was just wondering if it actually performs better than the JS built in Array#sort() method.

Maybe I'll fork and see if I can benchmark it

inspirit commented 11 years ago

there was one in the past: http://jsperf.com/sort-v8-copied/18

the idea behind is to make it generous as much as possible so u can sort anything and within any specified range

arnorhs commented 11 years ago

That's awesome. Do you know who the author of the algorithm is or is it just one of those general optimization techniques people try?

I've done some experiments with Introsort which is a quick sort + heap sort hybrid, but that did not have as good results.

Just wondering if the author would be offended if I plagiarized it..

inspirit commented 11 years ago

if u look in source u will find the comment:

// The current implementation was derived from *BSD system qsort(): // Copyright (c) 1992, 1993 // The Regents of the University of California. All rights reserved.

arnorhs commented 11 years ago

Ah, thanks. Not sure how I missed that. Should have rtfm

arnorhs commented 11 years ago

One more thing. Did you do the port from BSD's qsort? If not, where did the JS implementation come from?

inspirit commented 11 years ago

i ported it from C source code. there is no over JS versions. at least i dont know any.

arnorhs commented 11 years ago

Ah, I didn't know. Nice job!

The reason I'm so interested in it is that I need something similar for a project of mine.

It would be helpful if you would publish it as a stand alone module on npm. I'd be happy to do so and give you full credit and/or add you as a maintainer if that would be easier.

inspirit commented 11 years ago

well u can do it yourself i guess.

arnorhs commented 11 years ago

Thanks. Will do.

arnorhs commented 11 years ago

I published the module here: https://npmjs.org/package/qsort

I tried to give credit where I could and you are listed as the author in the package.json as well.

Thanks. Definitely faster on top of being able to sort partial sets. Awesome work.

inspirit commented 11 years ago

nice! thanx for the info :)