Chapter 2, Problem 4P

(a)

Program Plan Intro

To list the five inversions of the array $\langle 2,3,8,6,1\rangle$ .

(b)

Program Plan Intro

To find the most inversions from the set $\left\{1,2,\mathrm{...}n\right\}$ and also find the number.

(c)

Program Plan Intro

To find the relation between the running time of the insertion sort and the number of inversions in the input array.

(d)

Program Plan Intro

To describe an algorithm that finds the number of inversions in any permutations of n elements in $\Theta \left(n\lg n\right)$ time.