Question 15
Five cards, numbered 1 to 5, are arranged randomly in a row. They are sorted from smallest to largest using the “Bubble Sort” algorithm: starting from the left, compare the first two adjacent cards and swap them if the left card is bigger; then move one position to the right and repeat until reaching the end of the row. Repeat this procedure from the beginning until the cards are fully sorted.
Count every swap made during the entire process. For example, $(4,5,3,2,1)$ requires 9 swaps:
$$(4,5,3,2,1)\to(4,3,5,2,1)\to(4,3,2,5,1)\to(4,3,2,1,5)$$
$$\to(3,4,2,1,5)\to(3,2,4,1,5)\to(3,2,1,4,5)\to(2,3,1,4,5)$$
$$\to(2,1,3,4,5)\to(1,2,3,4,5).$$
How many initial arrangements require exactly 5 swaps to be fully sorted? Give a detailed solution.
Count every swap made during the entire process. For example, $(4,5,3,2,1)$ requires 9 swaps:
$$(4,5,3,2,1)\to(4,3,5,2,1)\to(4,3,2,5,1)\to(4,3,2,1,5)$$
$$\to(3,4,2,1,5)\to(3,2,4,1,5)\to(3,2,1,4,5)\to(2,3,1,4,5)$$
$$\to(2,1,3,4,5)\to(1,2,3,4,5).$$
How many initial arrangements require exactly 5 swaps to be fully sorted? Give a detailed solution.