61–70 of 110 posts
Earlier quoted context omitted.
I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
In place kinda means the opposite of in swap space.
(This sort does not use the term that way, but another sort could.)
Since we're already using O(N) space, it would be interesting to see how this compares to Radix sort[0], which is O(N) space but O(N) time ( due to just hashing everything ). Like others have said, it would be cool to see quadsort stacked up to other current state-of-the-art sorting algorithms. [0] https://en.wikipedia.org/wiki/Radix_sort
Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d...
Shameless self promotion, if you want a faster sorting implementation, check out pdqsort (https://github.com/orlp/pdqsort) which is almost twice as fast as libstdc++'s std::sort for randomly shuffled integers, and has all sorts of tricks for input distributions with patterns (like pre-sorted, reverse sorted, single out-of-order element appended, etc).
Since we're already using O(N) space, it would be interesting to see how this compares to Radix sort[0], which is O(N) space but O(N) time ( due to just hashing everything ). Like others have said, it would be cool to see quadsort stacked up to other current state-of-the-art sorting algorithms. [0] https://en.wikipedia.org/wiki/Radix_sort
Small nitpick: radix sort has nothing to do with hashing.
Earlier quoted context omitted.
Small nitpick: radix sort has nothing to do with hashing.
A radix sort is a type of hashing, no? You're bucketing the items based on a reduced form projection of them onto some smaller subspace.
Earlier quoted context omitted.
A truly optimal sorting for a given N is a nontrivial problem. By truly optimal I mean the actual absolute minimum in the number of comparisons, no O(...) approximation. For five elements the lower bound from counting the permutations is ceil(log2(5!)) which says you cannot sort 5 elements in less than 7 comparisons. An actual 7 comparison algorithm exists but it is not very easy to write it. For greater numbers it g…
Agreed. My use of the word "optimal" in the original comment was a bit careless.
C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... Shameless self promotion, if you want a faster sorting implementation, check out pdqsort ( https://github.com/orlp/pdqsort ) which i…
In his benchmark, the author is assuming that qsort() is implemented using quicksort, but that's not necessarily true. For example, glibc is using mergesort (although it falls back to quicksort if the system is short on memory).
I can’t imagine the sort of bugs you get when your code relies on stable sort but calls qsort and everything works great until the machine is under heavy load.
1000000 is peanuts. We need to see convergence for about billions+ of numbers.
Earlier quoted context omitted.
Small nitpick: radix sort has nothing to do with hashing.
A radix sort is a type of hashing, no? You're bucketing the items based on a reduced form projection of them onto some smaller subspace.