arrays - complexity - sorting algorithms comparison

¿Hay alguna forma de medir qué tan ordenada es una lista?

Question

¿Hay alguna forma de medir qué ordenada es una lista?

Quiero decir, no se trata de saber si una lista está ordenada o no (booleana), sino algo así como una proporción de "clasificación", algo así como el coeficiente de correlación en las estadísticas.

Por ejemplo,

• Si los elementos de una lista están en orden ascendente, entonces su tasa sería 1.0

• Si la lista se ordena de forma descendente, su tasa sería -1.0

• Si la lista está casi ordenada en forma ascendente, su índice sería de 0.9 o algún valor cercano a 1.

• Si la lista no está ordenada en absoluto (al azar), su tasa estaría cerca de 0

Estoy escribiendo una pequeña biblioteca en Scala para practicar. Creo que una tasa de clasificación sería útil, pero no encuentro información sobre algo así. Tal vez no conozco los términos adecuados para el concepto.

Answer 1

¿Qué tal algo como esto?

#!/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()

Answer 2

Además del recuento de inversión, para las listas numéricas, la distancia cuadrada media desde el estado ordenado es imaginable:

#! 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

Answer 3

Hubo excelentes respuestas, y me gustaría agregar un aspecto matemático para completar:

• Puede medir qué tan ordenada es una lista midiendo cuánto se correlaciona con una lista ordenada. Para hacer eso, puedes usar la correlación de rango (la más conocida es la de Spearman''s ), que es exactamente la misma que la correlación habitual, pero utiliza el rango de elementos en una lista en lugar de los valores análogos de sus elementos.

• Existen muchas extensiones, como un coeficiente de correlación (+1 para el tipo exacto, -1 para la inversión exacta)

• Esto le permite tener propiedades estadísticas para esta medida, como el teorema del límite central de permutaciones, que le permite conocer la distribución de esta medida para listas aleatorias.

Answer 4

La medida tradicional de cómo se ordena una lista (u otra estructura secuencial) es el número de inversiones.

El número de inversiones es el número de pares (a, b) índice st de a <b AND b << a. Para estos fines, << representa la relación de ordenamiento que elija para su tipo particular.

Una lista completamente ordenada no tiene inversiones, y una lista completamente revertida tiene el número máximo de inversiones.

Answer 5

No estoy seguro del "mejor" método, pero uno simple sería comparar cada elemento con el siguiente, incrementando un contador si elemento2> elemento 1 (o lo que sea que quiera probar) y luego divida por el número total de elementos. Debería darte un porcentaje.

Answer 6

Puedes usar la correlación real.

Suponga que a cada elemento de la lista ordenada, le asigna un rango entero comenzando desde cero. Tenga en cuenta que un gráfico del índice de posición de los elementos frente al rango se verá como puntos en línea recta (correlación de 1.0 entre la posición y el rango).

Puede calcular una correlación en estos datos. Para una clasificación inversa obtendrá -1 y así sucesivamente.

Answer 7

Si toma su lista, calcule los rangos de los valores en esa lista y llame a la lista de rangos Y y otra lista, X que contiene los enteros de 1 a length(Y) , puede obtener exactamente la medida de clasificación que usted es buscando mediante el cálculo del coeficiente de correlación , r , entre las dos listas.

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

Para una lista ordenada por completo, r = 1.0 , para una lista clasificada inversa, r=-1.0 , y la r varía entre estos límites para diversos grados de ordenamiento.

Un posible problema con este enfoque, dependiendo de la aplicación, es que calcular el rango de cada elemento en la lista es equivalente a clasificarlo, por lo que es una operación O (n log n).

Answer 8

Simplemente puede contar el número de inversiones en la lista.

Inversión

Una inversión en una secuencia de elementos de tipo T es un par de elementos de secuencia que aparecen desordenados de acuerdo con algún orden < en el conjunto de T ''s.

De la Wikipedia :

Formalmente, deje que A(1), A(2), ..., A(n) sean una secuencia de n números.
Si i < j y A(i) > A(j) , entonces el par (i,j) se llama inversión de A

El número de inversión de una secuencia es una medida común de su ordenamiento.
Formalmente, el número de inversión se define como el número de inversiones, es decir,

Para aclarar estas definiciones, considere la secuencia de ejemplo 9, 5, 7, 6 . Esta secuencia tiene las inversiones (0,1), (0,2), (0,3), (2,3) y el número de inversión 4 .

Si quiere un valor entre 0 y 1 , puede dividir el número de inversión entre N choose 2 .

Para crear realmente un algoritmo que calcule este puntaje según la clasificación de una lista, tiene dos enfoques:

Enfoque 1 (determinista)

Modifique su algoritmo de clasificación favorito para realizar un seguimiento de la cantidad de inversiones que está corrigiendo a medida que se ejecuta. Aunque esto no es trivial y tiene implementaciones variables según el algoritmo de clasificación que elija, terminará con un algoritmo que no es más caro (en términos de complejidad) que el algoritmo de clasificación con el que comenzó.

Si toma esta ruta, tenga en cuenta que no es tan simple como contar "swaps". Mergesort, por ejemplo, es el peor caso O(N log N) , sin embargo, si se ejecuta en una lista ordenada en orden descendente, corregirá todas N choose 2 inversiones. Eso es O(N^2) inversiones corregidas en operaciones O(N log N) . Por lo tanto, algunas operaciones deben corregir inevitablemente más de una inversión a la vez. Tienes que tener cuidado con tu implementación. Nota: puede hacer esto con complejidad O(N log N) , es simplemente complicado.

Relacionado: calcular el número de "inversiones" en una permutación

Enfoque 2 (estocástico)

• Pares de muestras aleatorias (i,j) , donde i != j
• Para cada par, determine si list[min(i,j)] < list[max(i,j)] (0 o 1)
• Calcule el promedio de estas comparaciones y luego normalícelo por N choose 2

Yo personalmente iría con el enfoque estocástico a menos que tenga un requisito de exactitud, aunque solo sea porque es muy fácil de implementar.

Si lo que realmente quieres es un valor ( z'' ) entre -1 (ordenado descendiente) a 1 (ordenado ascendente), puedes simplemente asignar el valor de arriba ( z ), que está entre 0 (ordenado ascendente) y 1 (ordenado descendente) ), a este rango usando esta fórmula:

z'' = -2 * z + 1

Answer 9

Yo contaría las comparaciones y lo dividiría entre el número total de comparaciones. Aquí hay un ejemplo simple de 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