A base 2 radix sort should work here. That is:
On the first pass, place all the even cards in bin 0 and the odds in bin 1.
On the second pass, place all the cards congruent to 0 or 1 mod 4 in bin 0,
and the rest in bin 1.
Continue until the stack is sorted (2^.N passes).
In J this is
step =. [: ; ] (</.~ {~ ~.@]) 2&|@:(<.@%~)
sort =: [: step&:>/ (<,~[:(<"0)2^[:i.@-@>.2^.#)
Marshall
On Tue, Aug 14, 2012 at 2:35 PM, 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.
>
> On Tue, Aug 14, 2012 at 6:58 PM, Roger Hui <[email protected]>
> wrote:
> > I assumed as much, and the algorithm I described would work for the
> > problem. If blank can be a character, then instead of j=9,8,7,...,0
> you'd
> > have j=9,8,7,...,0,' '.
> >
> >
> >
> > On Tue, Aug 14, 2012 at 10:05 AM, Ian Clark <[email protected]>
> wrote:
> >
> >> Perhaps it was misleading of me to mention card columns 73-80. This
> >> was just a field into which an integer 0-99999999 could be put, to
> >> number the cards in their correct sequence. I was assuming (as was the
> >> convention for a program or data deck of N cards) they were numbered 1
> >> to N. So it's just a problem of sorting numbered cards.
> >>
> >> On Tue, Aug 14, 2012 at 4:53 PM, Roger Hui <[email protected]>
> >> wrote:
> >> > There is a linear algorithm that takes 80*n passes, based on
> >> lexicographic
> >> > sorting.
> >> >
> >> > for k=80,79,..,73,
> >> > keep a separate stack of collected cards, initially empty
> >> > for j=9,8,7,...,0
> >> > output cards having value j in column k into hopper 2; the other
> >> cards
> >> > into hopper 1
> >> > put the cards from hopper 2 on top of the separate stack of
> collected
> >> > cards;
> >> > put cards from hopper 1 into the input hopper for the next j
> >> > put the separate stack of collected cards into the input hopper for
> the
> >> > next k
> >> >
> >> > I think there's a "sorting card reader" with multiple (at least 10?)
> >> output
> >> > hoppers that can do this more efficient, taking n passes for sorting n
> >> > columns.
> >> >
> >> >
> >> >
> >> > On Tue, Aug 14, 2012 at 8:24 AM, Ian Clark <[email protected]>
> >> wrote:
> >> >
> >> >> Puzzle...
> >> >>
> >> >> The IBM 1442 Card Reader http://en.wikipedia.org/wiki/IBM_1442 had
> two
> >> >> output hoppers. A deck of punched cards was generally numbered in
> cols
> >> >> 73-80. There was a program to sort a shuffled deck in several passes.
> >> >> Each pass would allocate cards to one or other hopper. The contents
> of
> >> >> hopper 2 were then piled on top of hopper 1 and the whole pile
> >> >> reloaded for another pass. When all the cards emerged in hopper 1,
> the
> >> >> stack was sorted.
> >> >>
> >> >> How did that program work?
> >> >>
> >> >> A naive algorithm for the first pass is to output cards to hopper 2
> >> >> until you hit card #0, sending it to hopper 1. If you subsequently
> hit
> >> >> card #1, send that to hopper 1 as well, and so on. That might be good
> >> >> enough to sort out the typical mishap of dropping the deck on the
> >> >> floor, which would leave longish sequences of cards in-order.
> >> >>
> >> >> But there's got to be a more efficient algorithm than that. The 1442
> >> >> sorting process is the inverse of the so-called riffle-shuffle of
> >> >> playing cards, which appears empirically to be pretty effective at
> >> >> randomizing cards in as few as 3 or 4 cuts. If you know how to
> specify
> >> >> a "minimal-pass" riffle-shuffle to generate any given permutation,
> >> >> then you've solved the problem. Then what's the expected number of
> >> >> cuts you'd need to generate a given permutation which is a random
> >> >> choice of all (equi-likely) permutations? I'd conjecture (2^.N) for a
> >> >> deck of N cards.
> >> >>
> >> >> Unlike other questions I've posted, I don't have an immediate use for
> >> >> the answer to this one. It's just been bugging me. I'm supposed to
> >> >> know something about permutations, but I can't seem to make any
> >> >> progress. Trying to visualize it evokes the "butterfly" of the
> >> >> Cooley-Tukey FFT algorithm, but that may be only a chimera.
> >> >>
> ----------------------------------------------------------------------
> >> >> For information about J forums see
> http://www.jsoftware.com/forums.htm
> >> >>
> >> > ----------------------------------------------------------------------
> >> > For information about J forums see
> http://www.jsoftware.com/forums.htm
> >> ----------------------------------------------------------------------
> >> For information about J forums see http://www.jsoftware.com/forums.htm
> >>
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
