Inversions in an Array: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 3: | Line 3: | ||
=Problem= | =Problem= | ||
Given an array containing n numbers, in an arbitrary order, find all '''inversions''', where an inversion is defined as a pair (i, j) of array elements where i < j and A[i] > A[j]. Note that i and j need not be adjacent (in this case the inversion is called "out of order"). | Given an array containing n numbers, in an arbitrary order, find all '''inversions''', where an inversion is defined as a pair (i, j) of array elements where i < j and A[i] > A[j]. Note that i and j need not be adjacent (in this case the inversion is called "out of order"). | ||
=Discussion= | |||
=TODO= | =TODO= | ||
Revision as of 17:50, 20 September 2021
Internal
Problem
Given an array containing n numbers, in an arbitrary order, find all inversions, where an inversion is defined as a pair (i, j) of array elements where i < j and A[i] > A[j]. Note that i and j need not be adjacent (in this case the inversion is called "out of order").
Discussion
TODO
- problem statement
- algorithm
- complexity with Master Method
Overview