River crossing with boat

Question

Alan, Bill, Charly, Dean and Edgar are going to cross a river to reach the opposite river bank by using a small boat. The rules are very strict because the river is deep and dangerous: For the boat not to sink, the 5 friends must be seated one behind the other, starting from the lightest, in order of weight. All friends are of different weight! All they have with them is a balance scale. Given that their time is limited, they must determine the order by the least number of weightings. Can you help them?

Starting with A+B we determine AB. Say we have $A>B$. Then we add C and weight it against, say, the lightest. $B+C$. If we have $C<B$ then $C<B<A$. But we can't go on with such a simplistic approach. There must be something clever which I am missing.

Answer 1

Edited to add: The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.

The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.

---

John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:

SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);

Here, SWAP(x,y) means "Swap x and y if x weighs more than y."

Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this: Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:

Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.

After the nine weighings in the list, have them line up in the order of the cards that they hold.