Quoting Online algorithm from Wikipedia:
In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
One is Insertion Sort, but it runs in horrible $O(n^2)$ time.
Asked By : uoɥʇʎPʎzɐɹC
Answered By : Evil
I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion).
In that case you can access sorted structure at any time.
If inputs comes in batches, sort batch (with any fast algoritm) and then merge.
Other algorithms will also suffer from divided input, but insertion sort is poor even if input is available at once.
Natural split into sorted parts occurs in Mergesort and Timsort. But overall performance should be adjusted to needs: if data comes one at the time, but there is no need to retreive sorted version, it would be nice to keep smaller sorted buffers.
When length of array is known in advance and distribution the set it is possible to do distribution based sort, it spares some empty cells for incomming data.
If data could be divided into ranges, this would enable partitioning of data as it arrives.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/55012
0 comments:
Post a Comment
Let us know your responses and feedback