3
$\begingroup$

Let $n > 1$ be an integer. Let $A$ be an array, indexed from $1$ to $n$, of $n$ values $A(i)$ coming from the finite set $\{0,1\}$. (More generally, the values can come from any totally ordered set, but I only need a two element set for now.)

Let us count the number of inversions in A, that is the number of pairs $(i,j)$ with $i < j$ and $A(i) > A(j)$. Using $[\quad ]$ for Iverson notation, this is

$$I = \sum_{ 1 \le i \le j \le n } [A(i) > A(j)]$$

I call the quantity $I/n^2$ the inversion density of $A$. As an exercise you can show the inversion density falls in the closed interval $[0, 1/4]$.

Question: Is this (inversion density) or a closely related concept present in the literature? If so, please tell me where.

I am still wading through the sorting literature, where number of inversions in an array are considered, but I have yet to see anything regarding a density. I have not yet found a successful online search; if a good search term is proffered I will try it as a substitute for a good reference.

Motivation: I did some research on Combsort and was looking for worst case complexity results. After finding some bad (good) cases, I saw that the same ideas had been more fully developed in the two papers listed below. In particular Poonen has a proposition which can be phrased in terms of inversion density as: there is an absolute constant $c$ so that, for any length $n$, $0$-$1$ array $A$ and for any integer $j$ with $1 < j \le n,$ there is a contiguous length $j$ subarray $B$ (so $B(k) = A(l+k-1)$ for some $l$ and $1 \le k \le j$ ) such that the inversion density of $B$ is at least $c$ times the inversion density of $A$.

Poonen shows $c \ge 1/256$. I can tighten his argument to show $c \ge 1/32$, and suspect $c = 1/2$. I also suspect the proposition holds for arrays with values from any totally ordered set.

References (Please add to this!):

Mark Allen Weiss and Robert Sedgewick, "Tight Lower Bounds for Shellsort", Journal of Algorithms Volume 11, Issue 2, June 1990, Pages 242-251

B. Poonen, “The worst case in Shellsort and related algorithms,” J. of Algorithms 15, 1993, 101-124.

Gerhard "Ask Me About System Design" Paseman, 2010.07.10

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.