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

34

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

Роберт С. Барнс
источник

Ответы:

31

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

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

n/2+1,n/2+2,,n,1,,n/2

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


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

Юхо
источник
2
Контекст пытается понять, почему быстрая сортировка работает относительно плохо на случайных перестановках n элементов, где число инверсий близко к медиане.
Роберт С. Барнс
1
Отличный пример, это именно та информация, которую я искал.
Роберт С. Барнс
1
Estivill-Кастро и Вуд ссылка на это точно.
Педро Дуссо
10

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

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

  1. Если отсортирован, то .XΣm(X)=0

  2. Если с , и для всех , тогда .X,YΣX=x1xnY=y1ynxi<xiyi<yji,j[1..n]m(X)=m(Y)

  3. Если является подпоследовательностью , то .XYΣm(X)m(Y)

  4. Если для всех и для некоторого , то .xi<yji[1..|X|]j[1..|Y|]X,YΣm(XY)m(X)+m(Y)

  5. m(aX)|X|+m(X) для всех и .XΣaEX

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

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

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

Pr(X)=θm(X)YΣΣ|X|θm(Y) .

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

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


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

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

Для любой последовательности [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 элемента. И когда последовательность была отсортирована, никакой работы не требуется.

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

Андрушенко Александр
источник
Хорошая идея. Аналогичное определение - Exc, третье определение беспорядка в статье, упомянутой в ответе Юхо . Exc - количество операций, необходимых для перестановки последовательности в отсортированном порядке.
Apass.Jack
Ну, может быть, я просто применил свое понимание энтропии и беспорядка к последовательности элементов :-)
Андрушенко Александр
-2

Если вам нужно что-то быстрое и грязное (знаки суммирования меня пугают), я написал супер-легкую функцию беспорядка в 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. Не сложно, но работает.

Майкл

Майкл Снебергер
источник
Это не сайт программирования. Было бы достаточно определить понятие беспорядка и упомянуть, что оно может быть вычислено за линейное время.
Юваль Фильмус