2 ms·
Fast median search: an ANSI C implementation (1998)
- sytelus 12y agoMany of O(n) algo for median have one compromise: They either return only the upper or lower median when n is even. In some applications, we might want average of these two instead. Are there any efficient algorithm there? Obviously it can be done with two calls to O(n) algo but can it be done more elegantly, efficiently and in single pass?
- cremno 12y ago>Every ANSI compliant C library comes with an implementation of a quicksort routine Actually the standard doesn't require qsort() to be quicksort. For example, musl's implementation uses the smoothsort algorithm. http://port70.net/~nsz/c/c11/n1570.html#7.22.5.2 http://port70.net/~nsz/c/c11/n1570.html#7.22.5.2 http://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c?id=aee9b1526247f74e9b755b50e102b3b4ce2aac1d http://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c?i...
- codezero 12y agoThe algorithm described as Torben's appears much earlier in Numerical Recipes for Fortran as a multi pass median that was designed to calculate medians from tapes where the memory was smaller than the storage device. Numerical Recipes cites Knuth's TAoCP I believe. The NR implementation is called mdian2 (for easy searching)