2

Consider a vector which goes in ascending order from (1, 2, 3 ... N). This vector is ordered 'correctly' and I would like to assign it a score of 1, which indicates a perfectly ascending ordered vector.

On the other hand, a vector (N, N-1, N-2 ... 3, 2, 1) has the 'worst' possible score of 0.

In between 0 and 1, the vector can be 'scrambled' and I would like a way to calculate how 'ordered' it is compared to the perfect case of (1, 2, 3 ... N).

Does anyone know of a way to calculate such a score which measures the ordered-ness of a vector?

Rachel
  • 23

2 Answers2

1

To start off you could measure the Inversion number of the vector.

In many cases the 'sortedness' measure is used to understand how many operations are needed to sort the vector using a particular algorithm. In that case, the measure of disorder could depend on the method used for sorting. It could be:

  • number of inversions
  • number of swaps
  • number of times a subsequence needs to be reversed etc

If you plan to use the sortedness measure to understand the effort in sorting the vector, look at this survey paper of sorting algorithms.

user1952500
  • 2,121
0

Here is one basic example.

In a vector of $n$ numbers, you will be making $n-1$ comparisons.

E.g. $x_1 \le x_2$ then $x_2 \le x_3$ up to $x_{n-1} \le x_n$.

Define the indicator variable $I_i$ to be $1$ if $x_i \le x_{i+1}$ and $0$ otherwise.

Then you can rate a vector of length $n$ on a level of "orderedness" like so: $$O(\mathbf{v}) = \frac{\sum_{i=1}^{n-1} I_i }{n-1}$$

In your two examples, this formula produces an "orderedness" value of $1$ and $0$ respectfully.

WaveX
  • 5,440