Inversions in an Array: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 2: | Line 2: | ||
* [[Algorithms#b3slp3|Algorithms | Divide and Conquer]] | * [[Algorithms#b3slp3|Algorithms | Divide and Conquer]] | ||
=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]. | 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"). | ||
=TODO= | =TODO= | ||
Revision as of 17:48, 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").
TODO
- problem statement
- algorithm
- complexity with Master Method
Overview