Есть ли способ измерить, насколько отсортирован список?

Я имею в виду, что речь идет не о знании, отсортирован ли список (булево), а о чем-то вроде коэффициента «сортировки», что-то вроде коэффициента корреляции в статистике.

Например,

• Если элементы списка расположены в порядке возрастания, тогда их скорость будет 1,0

• Если список отсортирован по убыванию, его скорость будет -1,0

• Если список почти отсортирован по возрастанию, его скорость будет 0,9 или какое-либо значение, близкое к 1.

• Если список не отсортирован вообще (случайно), его скорость будет близка к 0

Я пишу небольшую библиотеку в Scala для практики. Я думаю, что скорость сортировки была бы полезна, но я не нахожу никакой информации о чем-то подобном. Может быть, я не знаю адекватных терминов для концепции.

Вы можете просто посчитать количество инверсий в списке.

инверсия

Инверсия в последовательности элементов типа Tпредставляет собой пару элементов последовательности, которые появляются не по порядку в соответствии с некоторым порядком <на множестве T's.

Из Википедии :

Формально, пусть A(1), A(2), ..., A(n)будет последовательность nчисел.
Если i < jи A(i) > A(j), то пара (i,j)называется инверсией из A.

Число инверсии последовательности является одной из общих мер ее сортировки.
Формально число инверсии определяется как число инверсий, то есть

Чтобы сделать эти определения более понятными, рассмотрим пример последовательности 9, 5, 7, 6. Эта последовательность имеет инверсии (0,1), (0,2), (0,3), (2,3) и номер инверсии 4 .

Если вы хотите значение между 0и 1, вы можете разделить число инверсии на N choose 2.

Чтобы на самом деле создать алгоритм для вычисления этой оценки того, насколько отсортирован список, у вас есть два подхода:

Подход 1 (детерминированный)

Измените свой любимый алгоритм сортировки, чтобы отслеживать, сколько инверсий он исправляет во время работы. Хотя это нетривиально и имеет различные реализации в зависимости от выбранного вами алгоритма сортировки, вы получите алгоритм, который не дороже (с точки зрения сложности), чем алгоритм сортировки, который вы начали.

Если вы выберете этот маршрут, имейте в виду, что это не так просто, как подсчет "свопов". Например, Mergesort является наихудшим случаем O(N log N), но если он выполняется в списке, отсортированном в порядке убывания, он исправит все N choose 2инверсии. Это O(N^2)инверсии, исправленные в O(N log N)операциях. Поэтому некоторые операции неизбежно должны корректировать более одной инверсии за раз. Вы должны быть осторожны с вашей реализацией. Примечание: вы можете сделать это со O(N log N)сложностью, это просто сложно.

Связанный: вычисление количества «инверсий» в перестановке

Подход 2 (Стохастик)

• Случайно выбранные пары (i,j), гдеi != j
• Для каждой пары определите, list[min(i,j)] < list[max(i,j)](0 или 1)
• Вычислить среднее из этих сравнений, а затем нормализовать N choose 2

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

Если вы действительно хотите получить значение ( z') между -1(отсортировано по убыванию) в 1(отсортировано по возрастанию), вы можете просто отобразить значение выше ( z), которое находится между 0(отсортировано по возрастанию) и 1(отсортировано по убыванию), в этот диапазон, используя эту формулу :

z' = -2 * z + 1

Традиционной мерой того, насколько отсортирован список (или другая последовательная структура), является количество инверсий.

Количество инверсий - это количество пар (a, b) -го индекса a <b И b <<a. Для этих целей <<представляет собой любое отношение заказа, которое вы выбираете для вашего конкретного вида.

Полностью отсортированный список не имеет инверсий, а полностью перевернутый список имеет максимальное количество инверсий.

Вы можете использовать фактическую корреляцию.

Предположим, что каждому элементу в отсортированном списке вы назначаете целое число, начиная с нуля. Обратите внимание, что график индекса положения элементов в зависимости от ранга будет выглядеть как точки на прямой линии (корреляция 1,0 между позицией и рангом).

Вы можете вычислить корреляцию по этим данным. Для обратной сортировки вы получите -1 и так далее.

Там были отличные ответы, и я хотел бы добавить математический аспект для полноты:

• Вы можете измерить, насколько отсортирован список, измерив, насколько он соотнесен с отсортированным списком. Для этого вы можете использовать ранговую корреляцию (наиболее известной из которых является Спирмена ), которая в точности совпадает с обычной корреляцией, но она использует ранг элементов в списке вместо аналоговых значений своих элементов.

• Существует множество расширений, например коэффициент корреляции (+1 для точной сортировки, -1 для точной инверсии)

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

Помимо числа инверсий, для числовых списков можно представить среднеквадратичное расстояние от отсортированного состояния:

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

Я не уверен в «лучшем» методе, но простым было бы сравнить каждый элемент с последующим, увеличив счетчик, если element2> element 1 (или что вы хотите проверить), а затем разделить на общее число элементов. Это должно дать вам процент.

Я бы посчитал сравнения и разделил их на общее количество сравнений. Вот простой пример Python .

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result

Как насчет этого?

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()

Если вы возьмете свой список, вычислите ранги значений в этом списке и вызовете список рангов Yи другой список, Xкоторый содержит целые числа от 1до length(Y), вы можете получить именно ту меру сортировки, которую вы ищете, вычислив коэффициент корреляции , rмежду двумя списками.

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}} 

Для полностью отсортированного списка, r = 1.0для списка с обратной сортировкой r=-1.0, а также rразличия между этими пределами для различной степени сортировки.

Возможная проблема с этим подходом, в зависимости от приложения, состоит в том, что вычисление ранга каждого элемента в списке эквивалентно его сортировке, поэтому это операция O (n log n).