Sorting functions implemented in C as std qsort() format (opens in new tab)

(github.com)

41 pointsadembudak8y ago11 comments

11 comments

9 comments · 4 top-level

rambojazz8y ago· 4 in thread

Repo has no license.

That is a problem. Thankfully, the language in Github's terms of service mitigates this a bit, although it'd be still ideal for the author to add a license too:

"If you set your pages and repositories to be viewed publicly, you grant each User of GitHub a nonexclusive, worldwide license to use, display, and perform Your Content through the GitHub Service and to reproduce Your Content solely on GitHub as permitted through GitHub's functionality (for example, through forking)."

https://help.github.com/articles/github-terms-of-service/#4-...

ComputerGuru8y ago

I’ve never heard a less realistic / more cop-out licensing policy. You can reproduce it, but only on github. You can’t even clone it locally (as the license still applies to your fork).

It’s only there so you can’t sue GitHub for not detecting the lack of license and disabling the fork button.

1 more reply

graedus8y ago

Author has now added the "Do What The Fuck You Want Public License" (v2) [0]

[0] https://github.com/p1v0t/Sort/blob/master/LICENSE.md

userbinator8y ago

I would suggest public domain, if only for the fact that sorting algorithms don't really have much in the way of originality.

xiii14088y ago· 1 in thread

Very cool! The function pointers bother me a bit, but hey, I'm a C++ programmer, and maybe link-time optimization is there now.

jstimpfle8y ago

I've grown to like the plain C version. It has a very modular interface (doesn't require the sorted items to implements a certain protocol, i.e. "operator<"), and doesn't compile new code for each new type. (Often code size is the most important).

I think the worst case I measured is a factor of 2 in std::sort vs qsort on bare integers. On larger types it will be less. That's acceptable to me. Sorting is seldom the bottleneck (it's only important to do sort in many situations).

beeforpork8y ago

The overview table should list some important properties I find myself comparing when selecting a sort algo: (a) stack usage, (b) heap usage, (c) whether the algo is stable.

E.g., I am a big fan of heap sort, because the implementation is very simple, and non-recursive (O(1) stack), uses no heap, and has worst-case time O(log n). It is almost perfect, but it is not stable. Now, mergesort fixes that stability issue (and its implementation is usually also very simple), but is often recursive (like this implementation) and it usually requires 'malloc()', because it cannot easily be run in-place. In an overview list, this dilemma would be nicely visible.

rurban8y ago

I wonder why the better sorting algos are never compared, like for small integer indices counting sort is linear, for larger indices radix sort is optimal and for parallel sorting there exist also special variants.

j / k navigate · click thread line to collapse