Как измерить «сортировку»

Мне интересно, есть ли стандартный способ измерения "сортировки" массива? Будет ли массив с медианным числом возможных инверсий считаться максимально несортированным? Под этим я подразумеваю, что это в основном как можно дальше от сортировки или обратной сортировки.

Нет, это зависит от вашего приложения. Меры сортировки часто называют мерами беспорядка , которые представляют собой функции от до , где - это совокупность всех конечных последовательностей различных неотрицательных целых чисел. В обзоре Эстивилла-Кастро и Вуда [1] перечислены и обсуждены 11 различных показателей беспорядка в контексте алгоритмов адаптивной сортировки.$N^{<N}$$\mathbb{R}$$N^{<N}$

Количество инверсий может работать в некоторых случаях, но иногда недостаточно. Пример, приведенный в [1], представляет собой последовательность

который имеет квадратичное число инверсий, но состоит только из двух восходящих трасс. Это почти отсортировано, но это не захватывается инверсиями.

[1] Эстивилль-Кастро, Владмир и Дерик Вуд. «Обзор алгоритмов адаптивной сортировки». ACM Computing Surveys (CSUR) 24,4 (1992): 441-476.

Маннила [1] аксиоматизирует предварительную сортировку (с упором на алгоритмы, основанные на сравнении) следующим образом (перефразируя).

Пусть - полностью упорядоченное множество. Тогда отображение из (последовательности различных элементов из ) в натуральные является мерой предварительной сортировки, если оно удовлетворяет условиям ниже.$\Sigma$$m$$\Sigma^{\star}$$\Sigma$

1. Если отсортирован, то .$X \in \Sigma^{\star}$$m(X) = 0$

2. Если с , и для всех , тогда .$X,Y \in \Sigma^{\star}$$X = x_1 \dots x_n$$Y = y_1 \dots y_n$$x_i < x_i \iff y_i < y_j$$i,j \in [1..n]$$m(X) = m(Y)$

3. Если является подпоследовательностью , то .$X$$Y \in \Sigma^{\star}$$m(X) \leq m(Y)$

4. Если для всех и для некоторого , то .$x_i < y_j$$i \in [1..|X|]$$j \in [1..|Y|]$$X,Y \in \Sigma^{\star}$$m(X \cdot Y) \leq m(X) + m(Y)$

5. $m(a \cdot X) \leq |X| + m(X)$ для всех и .$X \in \Sigma^{\star}$$a \in E \setminus X$

Примерами таких мер являются

• количество инверсий,
• количество свопов,
• количество элементов, которые не являются максимумами слева направо, и
• длина самой длинной увеличивающейся подпоследовательности (вычитается из входной длины).

Обратите внимание, что случайные распределения с использованием этих мер были определены, то есть такие, которые делают последовательности, которые более / менее отсортированы, более или менее вероятно. Они называются Ewens-подобными распределениями [2, гл. 4-5; 3, пример 12; 4], частным случаем которого является так называемое распределение Мальвы . Веса параметрически в константе и выполняют$\theta > 0$

$\qquad\displaystyle \operatorname{Pr}(X) = \frac{\theta^{\,m(X)}}{\sum_{Y \in \Sigma^{\star} \cap \Sigma^{|X|}} \theta^{\,m(Y)}}$ .

Обратите внимание, как определяет равномерное распределение (для всех ).$\theta = 1$$m$

Поскольку существует возможность выборки перестановок по этим показателям эффективно, этот объем работы может быть полезен на практике при сравнительном анализе алгоритмов сортировки.

1. Меры предварительной сортировки и алгоритмы оптимальной сортировки Х. Маннила (1985)
2. Логарифмические комбинаторные структуры: вероятностный подход Р. Арратиа, А. Д. Барбура и С. Таваре (2003)
3. О добавлении списка чисел (и других одно-зависимых детерминантных процессов) А. Бородина, П. Диакониса и Дж. Фулмана (2010)
4. Ewens-подобные распределения и анализ алгоритмов Н. Auger et al. (2016)

У меня есть собственное определение «сортировки» последовательности.

Для любой последовательности [a, b, c,…] мы сравниваем ее с отсортированной последовательностью, содержащей одинаковые элементы, подсчитываем количество совпадений и делим ее на количество элементов в последовательности.

Например, для данной последовательности [5,1,2,3,4]мы действуем следующим образом:

1) отсортировать последовательность: [1,2,3,4,5]

2) сравнить отсортированную последовательность с оригиналом, переместив ее на одну позицию за раз и посчитав максимальное количество совпадений:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) Максимальное количество совпадений равно 4, мы можем рассчитать «сортировку» как 4/5 = 0,8.

Сортировка отсортированной последовательности будет 1, а сортировка последовательности с элементами, расположенными в обратном порядке, будет 1 / n.

Идея этого определения заключается в том, чтобы оценить минимальный объем работы, который нам потребуется для преобразования любой последовательности в отсортированную последовательность. В приведенном выше примере нам нужно переместить только один элемент, 5 (есть много способов, но перемещение 5 является наиболее эффективным). Когда элементы будут расположены в обратном порядке, нам нужно будет переместить 4 элемента. И когда последовательность была отсортирована, никакой работы не требуется.

Я надеюсь, что мое определение имеет смысл.

Если вам нужно что-то быстрое и грязное (знаки суммирования меня пугают), я написал супер-легкую функцию беспорядка в C ++ для класса с именем Array, который генерирует массивы int, заполненные случайно сгенерированными числами:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

Функция просто сравнивает значение в каждом элементе с индексом элемента + 1, так что массив в обратном порядке имеет значение беспорядка 1, а отсортированный массив имеет значение беспорядка 0. Не сложно, но работает.

Майкл