[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Length-unaware sorting algorithm
- From: Sean Conner <sean@...>
- Date: Thu, 25 Aug 2016 21:45:04 -0400
It was thus said that the Great Soni L. once stated:
> If you wanna try this as a challenge:
> (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
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.
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  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)
 Only 388 pages. And yes, that's 388 pages for Chapter 5 alone.