5 ms·
There are too many different tradeoffs and dimensions to the problem to say that one sorting algorithm is the "best". E.g. quicksort without fallback has a deni
by Aardwolf 7y ago
There are too many different tradeoffs and dimensions to the problem to say that one sorting algorithm is the "best". E.g. quicksort without fallback has a denial of service attack against it.
- matheusmoreira 7y agoInsertion sort is very interesting: as an online algorithm, it is capable of producing partial results.
- kadoban 7y agoI think you might mean selection sort, which picks out elements from the original in sorted order one at a time. Insertion sort has partial results early as well, but they probably wouldn't be as useful, the only thing you could report early would be "here's the sorted order of the first k elements in the list" (as opposed to the first k elements in sorted order from the whole list, that selection sort gives you). If you really did want online output like that, I think you'd want to look at heapsort instead. If you compare the worst-case you have O(n) time to prepare the heap (once at the start) and then O(lg n) time to produce each single element of the answer. Selection sort you'd require O(n) time to produce each element. Selection sort doesn't win out in average or best case either. The best you could really hope for is it to win on constant factors, but it'd be hard for realistic inputs.
- nwallin 7y agoI think the poster means you aren't given the completed set. Elements come dribbling in a few at a time. With insertion sort, you're able to say, "this is the sorted list at the time we know it right now." Obviously when you get the next element, you don't have a sorted list anymore; you have a sorted list and one extraneous element. But then you apply insertion sort iteration and have a sorted list again.
- kadoban 7y agoAh, yes that's true, good point. If that is the goal, BST sort might be a good idea as well (put elements into a balanced binary search tree as you receive them). Not _quite_ the same semantics (you don't have an array exactly at each step), but much faster asymptotics and should be able to answer any queries you'd be doing anyway.
- nwallin 7y agoYes, exactly. One thing to keep in mind is that it's surprisingly common for a sorted array to outperform a binary search tree because of cache locality and pointer indirection being slow, even though random inserts into arrays are slow. Especially for small sets or when reads greatly outnumber writes. Boost has flat_map and flat_set for this.
- CodesInChaos 7y agoSecurely random pivot selection would also avoid the DoS.
- GuB-42 7y agoSure, but secure RNGs are not cheap. That's another trade-off to consider.
- chkas 7y agoI think it should be enough to initialize the PRNG with a secure random value before sorting. Am I wrong?
- nwallin 7y agoIt kinda is. Use your operating system to get 128 random bits, use that as a key to AES, use AES-NI instructions to generate boat loads of more bits. These instructions can generate random bits faster than RAM can store them. Honestly, most of us mortals can operate on the assumption that thread local mt19937 PRNGs seeded with 19,937 OS provided secure bits is safe enough for secure quicksort pivot selection DOS protection, even if we can't generate crypto keys or nonces from it.