91–100 of 110 posts
Earlier quoted context omitted.
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
I agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
[1]: " rel="nofollow">https://en.wikipedia.org/wiki/Introsort>
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…
[1]: " rel="nofollow">https://en.wikipedia.org/wiki/Introsort>
How does this fare against Python's famous Timsort (used by several languages and systems)? How about the dual-pivot quicksort used by Java for primitive arrays? Someone has to have put together a nice benchmark for comparing many sorting algorithms. I wish that the author had done some benchmarking first, so that the proposed algorithm can properly be positioned w.r.t. state-of-the-art techniques.
Earlier quoted context omitted.
I agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
libstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort. [1]: " rel="nofollow">https://en.wikipedia.org/wiki/Introsort>
Oh lord it's almost 1k long
Earlier quoted context omitted.
I agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
libstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort. [1]: " rel="nofollow">https://en.wikipedia.org/wiki/Introsort>
Earlier quoted context omitted.
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.
Radix sort (similar to bucket sort) groups items based on individual digits of the non-hashed values. If you hash the values before, you will end up with the data being sorted according to their hash, but they will appear almost random in their unhashed form.
Earlier quoted context omitted.
The term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.
technically quick sort needs O(log N) additional space and it is still considered in-place. I guess the threshold for in-place-ness would be less than linear additional space?
Earlier quoted context omitted.
libstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort. [1]: " rel="nofollow">https://en.wikipedia.org/wiki/Introsort>
It's just quick sort with insertion sort for small base cases.
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.
You technically do not need any swap space to swap two numbers. So algorithms which only use swaps could be implemented fully in place.
[1] example: int a, b; a ^= b ^= a ^= b;