[Interest] qsort() Obsolete?

[Matthew Woehlke]

On 2015-04-17 08:17, Bo Thorsen wrote:
> On 04/17/2015 12:12 PM, Berkay Elbir wrote:
>> Hello All,
>>
>> I want to ask a question to you to be certain. Is void qsort() function
>> obsolete? Should we use std::sort instead of this function? Because I
>> have a priority list and need to sort it.
> 
> Slightly off-topic: Don't implement a priority queue this way. Unless
> you have a system where you get a bunch of those and can sort them once,
> and handle all of them. If this isn't the case, you are going to have
> inserts and removes mixed. Then you will continually sort something
> that's already sorted.

What Bo said.

If you need to be able to peek into the queue, the best you are probably
going to manage is to do a merge sort of all new items (which themselves
you can sort with std::sort). In the single insertion case this
degenerates into an insertion sort.

You might, if you are clever, turn inserts into a strict append into a
scratch array that isn't merged into the main queue until a read access
is attempted. This will let you batch insertions even if your public API
does not allow doing so, or if the producer needs to make separate
insertions for whatever reason, but the consumer is likely to not need
items until a number of insertions have happened.

If you don't need to peek into the queue (i.e. you use only push and pop
operations), and you don't have heavy batching, you're probably better
off implementing the queue as a binary heap. The underlying array is not
"sorted" as such, but push and pop operations are much faster
(guaranteed O(log N) vs. O(N)).

-- 
Matthew