Как определить, в какой степени / уровне массив чисел уже отсортирован

Question

Рассмотрим массив любых заданных уникальных целых чисел, например, [1,3,2,4,6,5] Как определить уровень "сортировки" в диапазоне от 0,0 до 1,0?

Answer 1

Один из способов - оценить количество элементов, которые необходимо переместить, чтобы отсортировать, а затем разделить их на общее количество элементов.

В качестве первого подхода я бы обнаружил первыйпросто количество раз, когда происходит переход от более высокого значения к более низкому.В вашем списке это будет:

3 -> 2
6 -> 5

для всего двух движений.Разделив это на шесть элементов, вы получите 33%.

В некотором смысле, это имеет смысл, поскольку вы можете просто переместить 2 между 1 и 3 и 5 между 4 и 6.

Теперь могут быть крайние случаи, когда более эффективно перемещать вещи по-другому, но тогда вам, вероятно, придется написать действительно сложные алгоритмы поиска, чтобы найти лучшее решение.

Лично я бы начал с самого простого варианта, который давал вам то, что вы хотели, и беспокоился о расширении, только если он окажется неадекватным.

Answer 2

На практике можно было бы измерить несортировку по количеству работы, которая необходима для сортировки.Это зависит от того, что вы считаете "работой".Если разрешены только обмены, вы можете посчитать количество необходимых операций обмена.Это имеет хорошую верхнюю границу (n-1).Для вида сортировки слиянием вас больше всего интересует количество прогонов, так как вам понадобятся шаги объединения (nrun).Статистически, вы, вероятно, могли бы принять «сумму (abs ((rank - намеренный_рань)))» в качестве меры, аналогичной тесту KS. Но на первый взгляд, такие последовательности, как «HABCDEFG» (7 перестановок, 2 прогона, промежуточное расстояние) и «HGFEDCBA»"(4 свопа, 8 пробежек, максимальное расстояние) всегда показывают упущения.

Answer 3

Вы можете суммировать расстояния до их отсортированной позиции для каждого элемента и делить их на максимальное число.

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;
}

Пример:

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

Answer 4

Я предложу другой подход: давайте посчитаем количество не убывающих последовательностей k в массиве, а затем возьмем его обращение: 1 / k .Для идеально отсортированного массива есть только одна такая последовательность: 1 / k = 1/1 = 1 .Этот уровень «несортированности» является самым низким, когда массив сортируется по убыванию.

0 уровень приближается только асимптотически, когда размер массива приближается к бесконечности.

Этот простой подход может быть вычислен за O (n) время.

Answer 5

Я бы сказал, что количество свопов не очень хороший способ определить это. Самое главное, потому что вы можете отсортировать массив, используя различное количество перестановок. В вашем случае вы можете переключать 2 <-> 3 и 6 <-> 5, но вы также можете сделать гораздо больше переключателей.

Как бы вы отсортировали, скажем:

1 4 3 2 5

Вы бы напрямую переключили 2 и 4 или 3 и 4, затем 4 и 2, а затем 3 и 2.

Я бы сказал, что более правильным методом будет количество элементов в нужном месте, деленное на общее количество элементов.

В вашем случае это будет 2/6.

Answer 6

Хорошо, это всего лишь идея, но что, если вы действительно можете отсортировать массив, т.е.

1,2,3,4,5,6

затем получите его как строку

123456

теперь получите исходный массив в строке

132465

и сравните расстояние Левенштейна между двумя

Answer 7

Одним из соответствующих измерений сортировки будет «количество перестановок, которые необходимо отсортировать».В вашем случае это будет 2, переключение 3,2 и 6,5.Тогда остается, как отобразить это на [0,1].Вы можете рассчитать максимальное количество перестановок, необходимое для длины массива, своего рода «максимальную несортируемость», которая должна дать значение сортировки, равное 0. Затем взять число перестановок для фактического массива, вычесть его из максимальногои разделите на макс.