[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Length-unaware sorting algorithm**
**From**: "Soni L." <fakedme@...>
**Date**: Thu, 25 Aug 2016 21:00:11 -0300

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.