Sorting algorithm for continuous data stream

Question

Which of the sorting algorithms heap-sort, quick-sort & merge-sort could work with a continuous stream of data? I want to have a list that's always sorted, so that new values can get into the list at the right location right away. I can't seem to find the specifics of always maintaining a sorted list and having a continuous data stream.

class StreamSorter<A extends Comparable <A>> { 
        // A[] sorted_list;
        // other fields and initialiser: TODO

 public void add_new_element(A x) {

 // add new element to the data received so far and create a sorted list.

  }
 }

How would this class be implemented, so that everytime add_new_element is called, the sorted_list contains all the sorted elements so far?

Sorry if this is a stupid question, believe me, I've looked as hard as I can.

Cheers

Can you clarify *continuous data stream*? If it means it's ongoing, then you can't really sort it since sort algorithms work on finite lists. You could sort it in blocks, but I don't think that's what you're asking. Or if you're taking in an input stream and keeping a list of everything seen so far, sorted, then an insertion sort would be appropriate. — lurker, Mar 30 '15 at 21:35
Rather than combining a sorting algorithm with an order-agnostic data structure, why not look for a data structure that *keeps* its elements sorted? Like a TreeBag/TreeMultiset or similar. You could alternatively write your own `List` subclass that overrides the `add()`/`insert()` methods and re-sorts itself after each call. — Craig Otis, Mar 30 '15 at 21:42
Take a look at [PriorityQueue](http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html). You can put objects into it and whenever you take them out, they will always come out in sorted order. — Misha, Mar 30 '15 at 21:46
Btw, in Java there are no underscores in method names (usually). The convention is to use camel case, as in `addNewElement`, a better alternative would be just `add`. — mike, Mar 31 '15 at 23:11

score 2 · Answer 1 · answered Mar 30 '15 at 21:55

You could use a TreeSet to maintain a sorted set and, if you need to, can wrap it in a thread safe wrapper using Collections.synchronizedSortedSet().

java.util.SortedSet<E> s = java.util.Collections.synchronizedSortedSet( new java.util.TreeSet<E>( new java.util.Comparator<E>(){
    @Override
    public int compare( final E o1, final E o2 ) {
        // Add sorting criteria.
        return 0;
    }
}));

score 1 · Answer 2 · answered Mar 30 '15 at 21:36

So, the thing is that can't really actually work. At any time, a new lowest element could come in and it'd have to go straight to the beginning, so you can't start going through the sorted list while more elements are still coming in. But a heap is sort of what you're looking for: you can add more elements to it, and you can work your way through it, taking off the lowest element you've seen so far.

score 0 · Answer 3 · edited May 23 '17 at 11:44

Since you said, I want to have a list that's always sorted, use a java.util.TreeSet<E> or a java.util.PriorityQueue<E>. The TreeSet implements the Set interface and thus allows no duplicate values.

Note that the inserted elements must have a natural ordering, i.e. implement Comparable<T> or you have to provide a Comparator<T>.

For further information on sorted datastructures take a look at following question here on stackoverflow.

score 0 · Answer 4 · answered Mar 30 '15 at 22:22

If I understand correctly - you want your elements stored in your in-momory collection in a sorted order on the fly and not sort it at a logical point when all elements are added to the collection.

If that is the correct understanding - you are looking for implementations of SortedSet - one of the examples being TreeSet.

Note that your elements need to be comparable. Limitation of course is in terms of memory utilization - considering the fact that you are streaming it is likely that you have relative larger data loads.

Quick and Dirty Example,

package com.mytrial;

import java.util.Set;
import java.util.TreeSet;


public class StreamSorterExample {

    private static class MyDataFromStream implements Comparable<MyDataFromStream> {
        int someWeight;

        public MyDataFromStream(int someWeight) {
            this.someWeight = someWeight;
        }

        @Override
        public String toString() {
            return Integer.toString(someWeight);
        }

        @Override
        public int compareTo(MyDataFromStream that) {
            return this.someWeight - that.someWeight;
        }
    };

    public static void main(String[] args) {
        Set<MyDataFromStream> streamedData = new TreeSet<MyDataFromStream>();

        streamedData.add(new MyDataFromStream(10));
        streamedData.add(new MyDataFromStream(3));
        streamedData.add(new MyDataFromStream(5));

        System.out.println(streamedData);

        streamedData.add(new MyDataFromStream(111));
        streamedData.add(new MyDataFromStream(-1));

        System.out.println(streamedData);
    };
};

Output

[3, 5, 10]
[-1, 3, 5, 10, 111]

Sorting algorithm for continuous data stream

4 Answers4