Inversions in an Array: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Algorithms#b3slp3|Algorithms | Divide and Conquer]] | * [[Algorithms#b3slp3|Algorithms | Divide and Conquer]] | ||
=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= | =TODO= | ||
<font color=darkkhaki> | <font color=darkkhaki> | ||
Revision as of 17:46, 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