Hi,
I have a queue which would keep on growing (random size) and for every push to the queue, I got to sort the data. I could simply say queue.sort() after every push to the queue but wondering what kind of sorting algorithm does sort() implements to understand if I need to implement a more efficient algorithm instead?
Thanks,
In reply to sjain12:
The LRM does not specify how a tool should implement a sorting method. But I’ve got to believe any built-in sorting method is going to be faster than what you could write just because of the direct access the tool has to the data. Also, since the queue is in mostly sorted order already, you will be near best case performance anyway for most sort algorithms.
But another factor you should consider is the choice of array type. Queues are very efficient when accessing the head or tail elements, but become very inefficient when accessing the middle elements. You might want to consider using a dynamic array where there is uniform access to every element. Resizing a dynamic array to grow by one element does not usually mean reallocating the entire array as much as you think it would.
You probably should try some experiments with your tool before making a decision.
In reply to dave_59:
Thanks Dave for your reply.
I agree queues are less efficient because of additional pointers. But resizing dynamic array by 1 element would lead to moving/copying the complete array content with each access which I am not sure is a good idea to do.
Instead it could be resized (may be add few elements at one go or double the exisiting array size everytime it reaches its max limit) might be better way to reduce frequent reallocation. What do you think?
In reply to sjain12:
Like I said above, resizing a dynamic array by one element may not be as expensive as you think. There is probably some padding based on the size of array being allocated.
You probably should try some experiments with your tool before making a decision.
In reply to dave_59:
Thanks Dave. Will try it out.