lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 



On 25/08/16 10:45 PM, Sean Conner wrote:

It was thus said that the Great Soni L. once stated:

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.)

   You're moving the goal posts YET AGAIN!  I quote from your question on
Code Challenge:

	The end of the array is a sequence of some value we'll call
	$PLACEHOLDER repeated for the same length as the array itself. You
	can (and should) use this to your advantage.
I meant you can use the fact that you have $ARRAY_LEN valid slots that all contain $PLACEHOLDER after $ARRAY_LEN to your advantage.
E.g. an array of length 2 isn't just {1, 2, nil}, it's {1, 2, nil, nil}, and slots beyond those are invalid (e.g. t[5] is invalid, t[4] is valid and gives you nil, t[0] is invalid). 

I thought that part was clear...



   In the case of Lua, $PLACEHOLDER is nil.

   So, can we use nil, or not?  What is the difference between ipairs()
stopping on a nil, and our code stopping on a nil?  Just how are we to
detemine the end of input?

   Soni, if you are *really* interested in the answer, I implore you to read
Chapter 5 of _The Art of Computer Programming_ by Donald Knuth.  It's a
quick read [1] that covers everything there pretty much is to know about
sorting and then some.  You should be able to find a copy via a library
(it's a bit pricy).

   -spc (More specifically, Chapter 5, section 2, "Internal Sorting".  That's
	an even quicker read at about 100 pages)

[1]	Only 388 pages. And yes, that's 388 pages for Chapter 5 alone.



--
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.