0

Say you have a list and you can invert initial segments of the list. You can get from 3-4-2-1-5 to 4-3-2-1-5 (invert the first two) and then to 1-2-3-4-5 (by inverting the first two).

Prove using induction that every sequence for n>=2 can be sorted with at most in 2n-3 inversions.

Gabe
  • 153

2 Answers2

3

The claim I will prove is that any string of $n$ numbers can be sorted in any way I want in at most $2n-3$ inversions.

Proof by weak induction over $n$:

Base: $n =2$. Then I have two numbers, which are either already in the order I want, which takes no inversions, or must be switched, which takes 1 inversion, so indeed at most $2n-3=4-3=1$ inversions.

Step:

Suppose I want to order $n$ numbers $1$ through $n$ in some way, but they are initially put in a random sequence. Now, let's say the order I want is $a_1 ... a_n$.

OK, suppose the number on the right is $a_i$

By inductive hypothesis, I can order the $n-1$ numbers to the left of $i$ in at most $2(n-1)-3$ inversions into the following order:

$a_n \: a_{n-1} ... \: a_{i+1} \: a_1 \: a_2 \: a_3 ... \: a_{i-1} \: a_i$

Now invert that whole string to

$a_i \: a_{i-1} ... \: a_3 \: a_2 \: a_1 \: a_{i+1} ... \: a_{n-1} \: a_n$

And then invert the first i numbers to get the desired sequence.

This takes 2 additional inversions, so the whole orignal sequence can be ordered in at most $2(n-1)-3+2=2n-2-3+2=2n-3$ inversions.

Bram28
  • 100,612
  • 6
  • 70
  • 118
2

This sort of sorting problem is called pancake sorting. Bill Gates made important contributions to the pancake sorting problem. Then he dropped out of school. He did all right for himself, though.

Base case:

$n = 2$

Either the sequence is already sorted, or it needs to be inverted and can be sorted with one inversion.

Inductive hypothesis:

Suppose a list of $n$ elements can be pancake-sorted in $2n-3$ (or fewer) flips.

We will need to show that a list of $n+1$ elements can be sorted in $2n-1$ (or fewer) flips.

With the first inversion, move the $(n+1)^{th}$ element to the front of the list. With the second inversion, invert the entire list, moving the $(n+1)^{th}$ element to the $(n+1)^{th}$ place.

Now you have $n$ elements still to sort. By the inductive hypothesis we can sort a list of n elements in $2n-3$ inversions or fewer.

We have shown that a list of $n+1$ elements can be sorted in $2n-1$ (or fewer) flips.

QED

Doug M
  • 57,877