¿Se garantiza que la función sorted() de python sea estable?

El documentation no garantiza eso. ¿Hay algún otro lugar donde esté documentado?¿Se garantiza que la función sorted() de python sea estable?

Supongo que podría ser estable ya que el método de ordenación en las listas es guaranteed to be stable (Notas 9no punto: "Comenzando con Python 2.3, el método sort() se garantiza estable"), y ordenado es funcionalmente similar. Sin embargo, no puedo encontrar ninguna fuente definitiva que lo diga.

Propósito: Necesito ordenar en base a una clave principal y también a una secundaria en los casos donde la clave primaria es igual en ambos registros. Si está garantizado que sorted() es estable, puedo ordenar la clave secundaria, luego ordenar la clave principal y obtener el resultado que necesito.

PD: Para evitar cualquier confusión, estoy usando estable en el sentido de "un tipo es estable si garantiza que no se cambia el orden relativo de los elementos que se comparan iguales".

Fuente

2009-12-16 sundar

Sí, la intención del manual es de hecho garantizar que sorted es estable y que utiliza exactamente el mismo algoritmo que el método sort. Me doy cuenta de que los documentos no son 100% claros sobre esta identidad; ¡los parches de doc son siempre felizmente aceptados!

Fuente

2009-12-16 15:36:08

He encontrado que si estoy ordenando tuplas o listas, cada vez que las claves de clasificación "primarias" son iguales, termina ordenando por la tecla "secundaria". Por ejemplo, 'ordenado ([(1, 2), (1, 1)])' devuelve '[(1, 1), (1, 2)]' en lugar de devolver la entrada original en la misma secuencia/orden. ¿No debería la garantía de estabilidad significa que debería devolver la entrada original '[(1, 2), (1, 1)]'? En ese caso, debe ser explícito y decir 'clasificado ([(1, 2), (1, 1)], clave = lambda t: t [0])' – ray

¿No es esto lo que se espera en este caso? Python comparará las tuplas a través de todos los elementos de manera predeterminada, no solo la primera "primaria". Si solo desea ordenar el primer elemento, puede pasar el parámetro 'clave' explícitamente. –

El "What's New" docs for Python 2.4 efectivamente establece que sorted() primero crea una lista, luego llama a sort() en ella, proporcionándole la garantía que necesita aunque no en los documentos "oficiales". También puede verificar la fuente, si realmente está preocupado.

Fuente

2009-12-16 15:38:39

¿Podría señalar dónde dice eso? Dice que sorted() "funciona como in-place list.sort()" y "una copia recién formada está ordenada", pero no lo veo diciendo que internamente use sort(). – sundar

La "copia" que se forma es una lista (eso es lo que obtienes como valor de retorno), y se llama a .sort() en esa lista antes de regresar. QED. No, no es una prueba irrefutable, pero hasta que Python tenga un estándar oficial, no lo conseguirás. –

Son stable. Aunque no necesita saber si la ordenación y la clasificación son estables, ya que no necesita ordenar en dos pasos cuando tiene varias claves.

Por ejemplo, si desea ordenar los objetos en función de sus last_name, first_name atributos, puede:

sorted_list= sorted(
    your_sequence_of_items, 
    key= lambda item: (item.last_name, item.first_name))

aprovechando la comparación tupla.

Esta respuesta, tal como está, cubre la pregunta original. Para otras preguntas relacionadas con la clasificación, está el Python Sorting How-To.

Fuente

2009-12-28 22:42:14 tzot

Esto puede tener un efecto no deseado si desea revertir el orden. Por ejemplo, al ordenar los productos, es posible que primero desee clasificar la calificación (orden ascendente) y luego el precio (también ascendente). Si invierte esto, quiere ordenar la clasificación en orden descendente, pero en precio en orden ascendente. Esto no funciona con esta solución. –

@RemcoWendt: no hay ningún requisito para lo que describes. En cualquier caso, considere 'key = lambda item: (-item.rating, item.price)' o proporcione un 'cmp' en lugar de un argumento' key'. Aunque todavía no estoy seguro del propósito de tu comentario. – tzot

De hecho, no era un requisito, pero quería señalar esta sutil diferencia cuando otras personas leen esto y eligen entre su solución o el uso de la función de ordenamiento estable de Python. –

Probablemente cambiado desde entonces, pero la documentación actual de sorted garantuees explícitamente:

la incorporada en sorted() función se garantiza que sea estable. Una ordenación es estable si garantiza que no se cambiará el orden relativo de los elementos que se comparan por igual; esto es útil para clasificar varias pasadas (por ejemplo, ordenar por departamento, luego por calificación salarial).

Fuente

2017-05-16 22:49:52 MSeifert

¿Se garantiza que la función sorted() de python sea estable?

Respuesta

Cuestiones relacionadas