¿Cómo puedo verificar si una lista está ordenada?

Question

Duplicar posible:
Pythonic way to check if a list is sorted or not

en Python, ¿Cómo puedo probar si una lista de números es ya ordenados o no?

Answer 1

some_list == sorted(some_list) 

Answer 2

Esto sólo es posible mediante la iteración en la lista (implícita o explícitamente):

all(b >= a for a, b in zip(the_list, the_list[1:]) 

Pero por qué no sólo una especie que si lo que habrá que resolver? El algoritmo de clasificación de Python será realmente barato en una lista ya ordenada, posiblemente más barata que la prueba anterior.

EDIT: Debido a esto se convirtió en una discusión sobre el rendimiento, aquí es una versión utilizando iteradores perezosos:

it = iter(the_list) 
it.next() 
all(b >= a for a, b in itertools.izip(the_list, it)) 

Para una lista ordenada al azar con un millón de entradas, esto es más de 10.000 veces más rápido que the_list == sorted(the_list).

Answer 3

Normalmente, ya debería saber si una lista está ordenada (porque así es como se define su entrada, o la ordenó previamente).

Si necesita verificar si una lista está ordenada porque, si no es así, desea ordenarla, simplemente ordene. Es una operación barata si la lista ya está ordenada, y no es mucho más costosa que verificar el pedido de manera explícita.

En otras palabras:

mylist.sort() 

ahora se sabe ordenadas.

Answer 4

if L == (lambda pp=[]: reduce(lambda p, i: pp.append(reduce(lambda t, i: 
     (lambda t, i, j: (lambda l=[]: map(lambda x: (lambda xx=l.append(1): 
     t[sum(l) - 1] if sum(l) not in map(1..__radd__, (i, j)) else (t[i] if 
     sum(l) == j + 1 else t[j]))(), t))())(t, i, i + 1) if t[i] >= t[i + 1] 
     else t, xrange(len(p) - 1), p)) or pp[-1], iter(lambda: len(pp) >= 2 
     and list.__eq__(*pp[-2:]), True), L))(): 
    print "yeah, it's sorted" 

Answer 5

Más un comentario en las otras respuestas que una respuesta, pero este sitio web hace los comentarios adecuados imposibles.

Las soluciones de clasificación son más rápidas si la lista ya está parcial o totalmente clasificada. Las soluciones iterativas son más rápidas si la lista es probable que esté en orden aleatorio, o si la lista está fuera de servicio desde el principio.

Esto es por dos razones. Primero, el género de Python es muy bueno cuando se le dan datos en un orden que entiende (parcialmente ordenado, revertido, etc.), pero si los datos son aleatorios o impredecibles, no puede ser mejor que cualquier otro tipo. En segundo lugar, la solución iterativa puede hacer un cortocircuito al lado de la falta de trabajo, si se descubre desde el principio que la lista no está ordenada.

Esto muestra los extremos opuestos:

import timeit, random, itertools 

def a(data): 
    return all(b >= a for a, b in itertools.izip(data, itertools.islice(data, 1, None))) 

def b(data): 
    return data == sorted(data) 

def main(): 
    data = range(1000000) 
    print "Sorted, iterative:", timeit.timeit(lambda: a(data), number=10) 
    print "Sorted, sort:", timeit.timeit(lambda: b(data), number=10) 

    random.shuffle(data) 
    print "Random, iterative:", timeit.timeit(lambda: a(data), number=10) 
    print "Random, sort:", timeit.timeit(lambda: b(data), number=10) 

resulta en estos tiempos en mi sistema:

Sorted, iterative: 1.42838597298 
Sorted, sort: 0.498414993286 
Random, iterative: 0.000043 
Random, sort: 10.5548219681 

Por lo tanto, en estos extremos el enfoque de clasificación es aproximadamente tres veces más rápido, y el enfoque lineal es aproximadamente ... doscientas mil veces más rápido.

Tenga en cuenta que la diferencia real aquí es no O (n) frente a O (n log n); la diferencia entre esas complejidades no es tan amplia. La principal diferencia es que la versión lineal puede cortocircuitar tan pronto como encuentre dos valores que están fuera de servicio, donde la versión de clasificación siempre tiene que hacer todo el trabajo.

Una implementación nativa podría obtener un rendimiento ideal de ambos, dando O (n) complejidad, la capacidad de cortocircuito y la baja sobrecarga del código nativo que hace que el método de clasificación sea más rápido. Si el rendimiento (¡y solo si!) Realmente importa, esa sería la solución correcta.

(Tenga en cuenta que normalmente no recomendaría elegir una solución basada en el rendimiento a menos que el rendimiento sea realmente un problema, pero vale la pena señalarlo ya que ninguno es mucho más simple que el otro. Entiendo, pero tampoco hay nada complejo en la versión iterativa.)