How to determine to which extent/level an array of integers is already sorted

Consider开发者_如何学JAVA an array of any given unique integers e.g. [1,3,2,4,6,5] how would one determine the level of "sortedness", ranging from 0.0 to 1.0 ?

---

One way would be to evaluate the number of items that would have to be moved to make it sorted and then divide that by the total number of items.

As a first approach, I would detect the former as just the number of times a transition occurs from higher to lower value. In your list, that would be:

3 -> 2
6 -> 5

for a total of two movements. Dividing that by six elements gives you 33%.

In a way, this makes sense since you can simply move the 2 to between 1 and 3, and the 5 to between 4 and 6.

Now there may be edge cases where it's more efficient to move things differently but then you're likely going to have to write really complicated search algorithms to find the best solution.

Personally, I'd start with the simplest option that gave you what you wanted and only bother expanding if it turns out to be inadequate.

---

I would say the number of swaps is not a very good way to determine this. Most importantly because you can sort the array using a different number of swaps. In your case, you could switch 2<-->3 and 6<-->5, but you could also do a lot more switches.

How would you sort, say:

1 4 3 2 5

Would you directly switch 2 and 4, or would you switch 3 and 4, then 4 and 2, and then 3 and 2.

I would say a more correct method would be the number of elements in the right place divided by the total number of elements.

In your case, that would be 2/6.

---

Ok this is just an idea, but what if you can actually sort the array, i.e.

1,2,3,4,5,6

then get it as a string

123456

now get your original array in string

132465

and compare the Levenshtein distance between the two

---

I'll propose a different approach: let's count the number of non-descending sequences k in the array, then take its reversal: 1/k. For perfectly sorted array there's only one such sequence, 1/k = 1/1 = 1. This "unsortedness" level is the lowest when the array is sorted descendingly.

0 level is approached only asymptotically when the size of the array approaches infinity.

This simple approach can be computed in O(n) time.

---

In practice, one would measure unsortedness by the amount of work it needs to get sorted. That depends on what you consider "work". If only swaps are allowed, you could count the number op swaps needed. That has a nice upper bound of (n-1). For a mergesort kind of view you are mostly interested in the number of runs, since you'll need about log (nrun) merge steps. Statistically, you would probably take "sum(abs((rank - intended_rank))" as a measure, similar to a K-S test. But at eyesight, sequences like "HABCDEFG" (7 swaps, 2 runs, submean distance) and "HGFEDCBA" (4 swaps, 8 runs, maximal distance) are always showstoppers.

---

You could sum up the distances to their sorted position, for each item, and divide with the maximum such number.

public static <T extends Comparable<T>> double sortedMeasure(final T[] items) {
    int n = items.length;

    // Find the sorted positions
    Integer[] sorted = new Integer[n];
    for (int i = 0; i < n; i++) {
        sorted[i] = i;
    }
    Arrays.sort(sorted, new Comparator<Integer>() {
        public int compare(Integer i1, Integer i2) {
            T o1 = items[i1];
            T o2 = items[i2];
            return o1.compareTo(o2);
        }
        public boolean equals(Object other) {
            return this == other;
        }
    });

    // Sum up the distances
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += Math.abs(sorted[i] - i);
    }

    // Calculate the maximum
    int maximum = n*n/2;

    // Return the ratio
    return (double) sum / maximum;
}

Example:

sortedMeasure(new Integer[] {1, 2, 3, 4, 5}) // -> 0.000
sortedMeasure(new Integer[] {1, 5, 2, 4, 3}) // -> 0.500
sortedMeasure(new Integer[] {5, 1, 4, 2, 3}) // -> 0.833
sortedMeasure(new Integer[] {5, 4, 3, 2, 1}) // -> 1.000

---

One relevant measurement of sortedness would be "number of permutations needed to be sorted". In your case that would be 2, switching the 3,2 and 6,5. Then remains how to map this to [0,1]. You could calculate the maximum number of permutations needed for the length of the array, some sort of a "maximum unsortedness", which should yield a sortedness value of 0. Then take the number of permutations for the actual array, subtract it from the max and divide by max.