Following your hints I tried to implement Mergesort for streams:.
I couldn’t get it to work though.
Besides it seems hardly a suitable algorithm for postponing evaluation, since the latter would only make sense during the final merge operation, when most of the work has already been done. Selection sort, though very inefficient for full sorting, is perhaps best suited for deferred partial (or incremental) sorting; that is when the exact number of elements required to be extracted is unknown beforehand.
So I tried to construct a Selection sort algorithm using Snap! streams.
I guess I would need to turn the list of unsorted elements into a stream, using the
block, thus creating a finite stream …
(As an aside, I’m puzzled by the SNAP! implementation of infinite vs. finite streams. I would have expected both of the following blocks to yield the same value, vid. “1” (one):
In reality only the first block yields “1”, the second yields a list with elements “1” and “2”. Is that even how it’s supposed to work?)
… and then I would need to write an algorithm extracting the smallest element from a finite set of numbers that is part of the stream, and modifying the stream to keep the other numbers for possible next increments. I haven’t figured out that algorithm yet.
So I developed my own (alas completely problem-specific) version of a lazy list of items to be sorted one at a time. Perhaps you (or some other reader) would be willing to show me how to turn this idea into a Snap!-style stream a/o algorithm? Thanks again!
Preparation: I devised my own Mickey Mouse version of a lazy list: item 1 contains evaluated (= sorted) values, item 2 holds unsorted values; the algorithm is not a part of the lazy list. Initially all values are in item 2:
Incremental sorting: the smallest value of the unsorted bunch is reported, and transfered to to the sorted queue:
Random access: to any item of the (virtual) sorted queue. If necessary, it will be calculated (as will all values before it within the sorted queue):
This algorithm, or alternatively the (non-incremental) Tournament sort I developed from other forum contributors’ hints, works well enough for my current application, but I’m truly interested to understand how streams work and how they can be applied.