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
– lurker, Commented Mar 30, 2015 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
– Craig Otis, Commented Mar 30, 2015 at 21:42
Take a look at PriorityQueue. You can put objects into it and whenever you take them out, they will always come out in sorted order. — Misha
– Misha, Commented Mar 30, 2015 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
– mike, Commented Mar 31, 2015 at 23:11

MT0 · Accepted Answer · 2015-03-30 21:55:57Z

2

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;
    }
}));

answered Mar 30, 2015 at 21:55

MT0

173k12 gold badges70 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Louis Wasserman · Accepted Answer · 2015-03-30 21:36:21Z

1

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.

answered Mar 30, 2015 at 21:36

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 11:44:37Z

0

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.

edited May 23, 2017 at 11:44

CommunityBot

11 silver badge

answered Mar 30, 2015 at 21:47

mike

5,0754 gold badges48 silver badges85 bronze badges

Comments

Y123 · Accepted Answer · 2015-03-30 22:22:45Z

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]

Collectives™ on Stack Overflow

Sorting algorithm for continuous data stream

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related