Inversions in an Array: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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").
This problem is interesting because it provides a "numerical similarity" measure that quantifies how close two ranked lists are to each other. If two friends rank the same ten movies to least favorite to most favorite. Computing the number of inversions between these two arrays gives a measure of "dissimilarity" between the preference in movies: more inversion, more dissimilar the preferences.


=Discussion=
=Discussion=

Revision as of 17:53, 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").

This problem is interesting because it provides a "numerical similarity" measure that quantifies how close two ranked lists are to each other. If two friends rank the same ten movies to least favorite to most favorite. Computing the number of inversions between these two arrays gives a measure of "dissimilarity" between the preference in movies: more inversion, more dissimilar the preferences.

Discussion

TODO

  • problem statement
  • algorithm
  • complexity with Master Method

Overview


[Next]