HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why are inversions useful in computer science?

Submitted by: @import:stackexchange-cs··
0
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).

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.