3 ms·
qsort() not good enough for you? (More realistically, below people are discussing that in the kernel environment the set of standard or third party library ava
by pjc50 4y ago
qsort() not good enough for you?
(More realistically, below people are discussing that in the kernel environment the set of standard or third party library available may be unavoidably limited)
- jart 4y agoqsort() is pretty slow if you're sorting something like long[]. In that case, radix sort goes 5x faster and vectorized quicksort goes 10x faster. If you're sorting int[] then vectorized quicksort goes 25x faster than qsort(). Nothing goes faster. The issue is it's a big ugly c++ monstrosity that's a huge pain to compile.
- rcxdude 4y agoThat's fair if the constant factor is relevant, but if bubble sort is terminating in any reasonable timescale then the difference between qsort, C++ std::sort, and a custom implementation is really not a factor.
- jart 4y agoPeople who don't compute much data don't need computer science.
- paulddraper 4y agoBut if you're comparing to bubblesort.....
- nice2meetu 4y agoThere is a quirk (almost a bug?) in FreeBSD's qsort where it will switch to insertsort for the whole array under certain conditions, which we hit in production given how our data was arranged. (I think this was the check) https://github.com/freebsd/freebsd-src/blob/main/lib/libc/stdlib/qsort.c#L171 https://github.com/freebsd/freebsd-src/blob/main/lib/libc/st...
- stefan_ 4y agoI like how someone felt the need to write out insertion sort in some 4 line code golf challenge in the midst of qsort. This right here is why no one wants to deal with C anymore.
- erk__ 4y agoDid a bit of digging and found that there used to be a comment for why it was done, but it got removed [0] when they switched to the implementation from Bentley & McIlroy's "engineering a sort function" [1] around 1992. [0]: https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb346606f3e100c17a565b1cc2f#diff-80cbaaf17a9c3baf31292416f97d13837515bdc13c94eedc285a79504409c708L167-L181 https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb... [1]: https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi...
- JdeBP 4y agoNonetheless, qsort() is available in libkern.
- canucker2016 4y agoNot at the time that the bubble-sort code was used though. see https://news.ycombinator.com/item?id=36005209 https://news.ycombinator.com/item?id=36005209
- JdeBP 4y agoYou mean written. It's been available for many of the years that it has been used. (-:
- IshKebab 4y agoNo. In most languages sorting a container is `foo.sort()` or something similar. `qsort()` is much more faff. I mean, clearly it wasn't good enough otherwise they would have used it, no? Perhaps integrating it was a huge faff.