The algorithm I described is O(n) and is therefore optimal. There is an unstated requirement in these procedures. A human operator of the card reader is involved, and it's desirable that what he/she is required to do is as straightforward as possible.
On Tue, Aug 14, 2012 at 11:35 AM, Ian Clark <[email protected]> wrote: > Then I think this is the same as the "naive algorithm" I described > (perhaps inadequately) which, at each pass, moves to a growing > sequence at the bottom of the deck, card #0, #1, #2, etc., (plus any > unbroken sequence that follows a given card). Needing N passes in the > worst case, to sort N cards. > > Maybe the IBM 1130 card-sorting program was no cleverer than this (I > never used it that much), but I have a strong feeling it's possible to > do much better. > > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
