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 <code>i < j</code> and <code>A[i] > A[j]</code>. | ||
=TODO= | =TODO= | ||
Revision as of 17:47, 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].
TODO
- problem statement
- algorithm
- complexity with Master Method
Overview