2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Pick your favorite sorting algorithm, and define the sortedness as the number of iterations required. $\endgroup$
    – David P
    Apr 24 '19 at 20:40
  • $\begingroup$ Or count the number consecutive values that are in ascending order $a$ and divide by $n-1$. $\endgroup$ Apr 24 '19 at 20:52
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.