3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ How your input looks like? Why online algorithm? $\endgroup$
    – Evil
    Commented Mar 27, 2016 at 16:28
  • $\begingroup$ @EvilJS Theoretical problem. $\endgroup$
    – noɥʇʎԀʎzɐɹƆ
    Commented Mar 27, 2016 at 17:47
  • 1
    $\begingroup$ Why is that time horrible? You don't even know that a faster one exists! $\endgroup$
    – Raphael
    Commented Mar 27, 2016 at 18:30
  • 3
    $\begingroup$ I don't understand your model. Why not just wait for all the input to arrive and store it ($O(n)$ time), then sort it with your favorite sorting algorithm? $\endgroup$
    – usul
    Commented Mar 29, 2016 at 14:10
  • 1
    $\begingroup$ What is the advantage of an "online algorithm" here? If the smallest element in the sequence is the last one, any correct sorting algorithm must wait for it to arrive before producing the first output. $\endgroup$
    – Pseudonym ♦
    Commented Mar 18, 2018 at 22:49

4 Answers 4

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You haven't explained why treesort is better than alternatives. As answered it looks more like your personal opinion. Can you elaborate? $\endgroup$
    – Johan
    Commented May 3, 2016 at 13:31
  • 1
    $\begingroup$ You suggest tree sort, but you don't provide any reasoning why tree sort would be better than say merge sort of whateverother-sort. $\endgroup$
    – Johan
    Commented May 3, 2016 at 16:57
  • 1
    $\begingroup$ @Johan ok, the merge sort with added one point at the time sorts everything or in good case it shifts array - this is costly operation. The Tree Sort as dynamic structure does not have this problem. The "better" is task dependent, in case of running case of adding points making full sorting per point will be in fact n^2logn, so it is not very good option. Splitting parts of data into batches and then merging is better when the batches are bigger and the sorted data is not needed per point. If this is not at all helpful maybe you could point what should be added or swing by chat? $\endgroup$
    – Evil
    Commented May 3, 2016 at 17:21
4
$\begingroup$

Heapsort is O(nlogn), but with a heap you can insert each element with O(logn). The benefit of this is that you always have access to your max and minimum element and can access them in O(1) time.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ You don't necessarily have access to max and min elements in O(1) time. If you use a max heap or min heap, then you only have access to one of those two. You only have access to both if you use a min-max heap. $\endgroup$
    – Jim Mischel
    Commented Dec 8, 2017 at 18:30
3
$\begingroup$

Depends on how you measure fast. Are you interested in squeezing out milliseconds or just in big O running time?

Insertion's sort O(n^2) may not be as horrible as it may seems with proper implementation. If you use binary search for finding the the insertion point your comparisons go down to O(log n) and if you move memory efficiently you can squeeze out quite a bit of performance.

For comparison on my system binary search saves about a second and a half for sorting 40 000 ints.

$ ./engine.exe 40000

binary_insertion_sort()
Swap: 399585418 swaps
Comp: 596083 comparisons
Time: 14.566 sec

insertion_sort()
Swap: 399585418 swaps
Comp: 399625411 comparisons
Time: 16.119 sec

Similarly, moving 100 000 000 ints one to the left takes 0.5790s with a for loop and only 0.2180s with memmove().

Depending on the size of your data set and the architecture you're running it on it may prove perfectly usable, especially online.

Not all O(n^2) algorithms are created equal, even though they are still O(n^2) at the end of the day.

Improve this answer
$\endgroup$
1
$\begingroup$

The time is $O (n^2)$, but only with the usual definition of "sorted": That we have an array of consecutive elements in ascending order. With that data structure, adding another element even if we know exactly where it belongs, takes time proportional to n on average, because in an array we have to move all elements along to insert one.

If we redefine sorted as "there is a way to traverse all items in ascending order quickly", then we can have for example a sorted tree much faster than $O (n^2)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.