Minimum adjacent swaps

Logical thinking · Suggested grades 6

Use inversion count and a matching construction to prove the minimum number of adjacent swaps.

Download video
Open Chinese transcript
  1. 数卡排成三、二、一,每次只能交换相邻两张。目标是排成一、二、三。
  2. 三二一里有三对顺序颠倒:三和二、三和一、二和一,所以至少需要消掉三个逆序。
  3. 第一次交换前两张,三二一变成二三一,只消掉三和二这一对。
  4. 第二次交换后两张,二三一变成二一三;第三次再交换前两张,得到一二三。
  5. 一次相邻交换最多减少一个逆序对,所以不可能少于三次;这条路线正好用了三次。
  6. 最少次数就是三。每次只交换相邻两张,并把交换前后的顺序写下来,就不容易漏步。
Sources for this explanation

Logical thinking

Count reversed pairs for a lower bound, then exhibit a route with that many swaps.

Worked example

Cards are 3, 2, 1. Only adjacent cards may be swapped. What is the minimum swaps to reach 1, 2, 3?

There are three inversions and each adjacent swap removes at most one. A three-swap route exists, so the minimum is 3.

Try one question

Minimum adjacent swaps from 2,1,3 to 1,2,3?