Google's analysis of gorosort includes the following comment:
At each move, "he needs to ensure that for each element x that is permuted,
the element in x's correct position is also permuted. This means he actually
has some choice about what to do."
It is fun to flesh this out a bit.
It is interesting to note that the out-of-place elements of an unsorted list
(with distinct elements) consist of a collection of non-overlapping loops.
For example, "2 1 4 5 3" consists of a loop of length two ("2 1") and a list
of length three ("4 5 3"). (My son Paul Johnson, an awesome code jammer ;-)
pointed this out to me.)
During the contest, I was trying to decide, for an input such as "2 1 4 3",
whether goro's algorithm should work on "2 1" first (do small loops one at a
time), or work on all unsorted elements together.
Turns out it doesn't matter. At each move goro can choose one or more
loops, and do those. If goro always chooses the entire set of out-of-order
elements, he has chosen the maximal set of loops available at each
iteration. But he can just as well choose a single doubleton loop "2 1", or
all of the doubletons, or a few doubletons, tripletons, and googletons
(assuming the list is long).
In each case, no matter what he does, he is expected on average to get one
more element in its proper place.
Greg Johnson
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
