Math Detours · Grade 7 · Around the corner · 19

How to sort a hand of cards

Swap neighbours until nothing is out of order. Count the swaps, find the worst case, and meet a faster way.

Name ____________________Date ____________

Tonight's idea

You hold a jumbled row of cards. Go along the row from the left. Whenever a card is bigger than the card on its right, swap the two. Then start again. Stop when a whole pass needs no swap. This is bubble sort: big cards bubble to the right.

3 1 4 2 swap 1 3 4 2 swap 1 3 2 4 swap 1 2 3 4 sorted
3 1 4 2 is sorted in three swaps.

How many swaps? If a bigger card is anywhere left of a smaller one, call the two an out-of-order pair. Swapping two neighbours puts that one pair right and changes no other pair, because no other card moved. So swaps = out-of-order pairs.

The worst hand is completely backwards: every pair is out of order. Each of \(n\) cards pairs with \(n - 1\) others, and that counts every pair twice.

Worst case for \(n\) cards: \(\dfrac{n(n - 1)}{2}\) swaps.

A faster idea is merge sort: split the hand in half, sort each half, then merge the two piles by always taking the smaller top card. For 1,000 cards that takes under 10,000 comparisons; bubble sort can need 499,500 swaps.

Watch one: 4 2 3 1

The 4 is left of 2, 3 and 1: three out-of-order pairs. The 2 and the 3 are each left of 1: two more. Five pairs, so expect five swaps.

Now sort: 4 2 3 1 → 2 4 3 1 → 2 3 4 1 → 2 3 1 4 → 2 1 3 4 → 1 2 3 4.

Five swaps, one short of the worst case for four cards, \(\dfrac{4 \times 3}{2} = 6\).

Halving is what makes merge sort fast. Try it in a guessing game: mathdetours.com/demos/guess.html.

Your turn

  1. Bubble sort the hand 2 4 1 3. Write the row after every swap and count the swaps.
  2. Without sorting, list the out-of-order pairs in 5 1 4 2 3. How many swaps will bubble sort need?
  3. How many swaps does bubble sort need in the worst case for (a) 6 cards, (b) 10 cards, (c) a full deck of 52 cards?
  4. A hand of 7 different cards needs 15 swaps. Now turn the hand around, so the row reads right to left. How many swaps does the turned hand need? Explain using pairs.

Stretch: a typical hand

Use the idea in exercise 4 to find the average number of swaps bubble sort needs, taken over every possible order of \(n\) different cards. What is the average for a deck of 52?

Answers

  1. 2 4 1 3 → 2 1 4 3 → 2 1 3 4 → 1 2 3 4. Three swaps. (The out-of-order pairs were 2 and 1, 4 and 1, 4 and 3.)
  2. 5 with 1, 5 with 4, 5 with 2, 5 with 3, 4 with 2, 4 with 3. Six pairs, so six swaps.
  3. (a) \(\dfrac{6 \times 5}{2} = 15\). (b) \(\dfrac{10 \times 9}{2} = 45\). (c) \(\dfrac{52 \times 51}{2} = 1326\).
  4. 6. Seven cards make \(\dfrac{7 \times 6}{2} = 21\) pairs. Turning the hand around flips every pair: one that was in order is now out of order, and the other way round. The first hand had 15 out-of-order pairs, so 6 were in order, and those 6 are the out-of-order pairs now.

Stretch. Match each order with its turned-around partner. By exercise 4 the two together always need \(\dfrac{n(n - 1)}{2}\) swaps, so they average half of that each. Every order is in exactly one such couple, so the average over all orders is \(\dfrac{n(n - 1)}{4}\), half the worst case. For 52 cards: \(\dfrac{52 \times 51}{4} = 663\).

← PreviousNext: Calculating with beads →