On Thu, Aug 25, 2016 at 4:33 PM, Phil Bewig <pbewig@gmail.com> wrote:
Insert items into a priority queue as they arrive. Extract the items from
the priority queue after all the items have arrived.
On Aug 25, 2016 6:19 PM, "Tim Hume" <tim@nomuka.com> wrote:
Well I guess you could just grab data as they arrive and keep on inserting
them into the correct position in a growing list of sorted data you've
already received? It might not be very efficient though.
Cheers,
Tim Hume
On Thu, 25 Aug 2016, Soni L. wrote:
Have y'all noticed how pretty much all sorting algorithms rely on length?
Are there any sorting algorithms that aren't explicitly aware of the
sequence/array length, and instead just happen to produce a sorted array?
(i.e. a sorting algorithm that doesn't rely on # or manual length
calculations, and doesn't explicitly try to find the boundary where the
array ends.)
Even the current Lua sorting algorithm uses the table length. Would be
interesting if there was a sorting algorithm about as fast as Lua's current
sorting algorithm, but without relying on length.
Phil describes heapsort, and this is exactly the use case heapsort was
designed for.
Tim describes insertion sort, which is less efficient than heapsort
but still better than it sounds on paper.
Both are reasonable choices; insertion sort's simplicity of
implementation makes it attractive.
/s/ Adam
