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

How to measure "sortedness"

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
measuresortednesshow

Problem

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean it's basically as far as possible from being either sorted or reverse sorted.

Solution

No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the context of adaptive sorting algorithms.

The number of inversions might work for some cases, but is sometimes insufficient. An example given in [1] is the sequence

$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n, 1, \ldots, \lfloor n/2 \rfloor \rangle$$

that has a quadratic number of inversions, but only consists of two ascending runs. It is nearly sorted, but this is not captured by inversions.

[1] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

Context

StackExchange Computer Science Q#11836, answer score: 35

Revisions (0)

No revisions yet.