Inversions

• Suppose we are given a list of elements L, of size n.

• Let i, and j be chosen so 1?i<j?n.

• If L[i]>L[j] then the pair (i,j) is an inversion.

1

2

3

4

5

6

7

8

9

10

Inversion

Inversion

Inversion

Not an Inversion

Previous slide

Next slide

Back to first slide

View graphic version