If I is the number of inversions in an input array of n records, then {Insertion|Bubble} Sort will require how many swaps?

I
  • n - I
  • I - n
  • n
  • n^2/2
  • I + n
  • I - 1
  • n - 1

An inversion requires a swap to undo it.

The number of comparisons done by an algorithm is generally different from the number of swaps.