patternMinor
Why are inversions useful in computer science?
Viewed 0 times
sciencewhyinversionsarecomputeruseful
Problem
In the second chapter of Cormen's textbook on Algorithms, he lists a discrete mathematics exercise on so-called "inversions", defined as follows:
Let $A[1 \ldots n]$ be an array of $n$ distinct numbers. If $i A[j]$, then the pair $(i, j)$ is called an inversion of $A$.
Question: Is this a mathematical concept that is used frequently in computer science? Are there some widely known applications of inversions that other people here know of? (I checked the wikipedia page for the concept, but it didn't list any).
Let $A[1 \ldots n]$ be an array of $n$ distinct numbers. If $i A[j]$, then the pair $(i, j)$ is called an inversion of $A$.
Question: Is this a mathematical concept that is used frequently in computer science? Are there some widely known applications of inversions that other people here know of? (I checked the wikipedia page for the concept, but it didn't list any).
Solution
To analyse many algorithms, in particular for the all-important sorting problem, the characteristics of permutations are important measures. For instance, the number of inversions determines the number of data movements when running insertion sort.
Context
StackExchange Computer Science Q#45644, answer score: 4
Revisions (0)
No revisions yet.