Re: Length-unaware sorting algorithm

["Soni L." <fakedme@...>]

On 25/08/16 08:19 PM, Tim Hume 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.

If you wanna try this as a challenge: 
http://codegolf.stackexchange.com/questions/91143/sort-an-array-without-knowing-its-length#

(And no, ipairs() and stuff is not allowed. ipairs() looks for the first 
nil and treats that as the array boundary, which in this case counts as 
an explicit length calculation.)

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.