lista - sorted python 3

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

Question

La documentation no garantiza eso. ¿Hay algún otro lugar donde esté documentado?

Supongo que podría ser estable, ya que se garantiza que el método de clasificación en las listas sea ​​estable (Notas 9º punto: "Comenzando con Python 2.3, el método sort () está garantizado para ser estable"), y ordenado es funcionalmente similar. Sin embargo, no puedo encontrar ninguna fuente definitiva que lo diga.

Objetivo: Necesito ordenar en base a una clave primaria y también una clave secundaria en los casos en que la clave principal 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 confusiones, estoy usando estable en el sentido de "un tipo es estable si garantiza no cambiar el orden relativo de los elementos que se comparan iguales".

Answer 1

El Python 3.6 doc on sorting ahora declara que

Las clases están garantizadas para ser estables

Además, en ese documento, hay un enlace al Timsort estable, que establece que

Timsort ha sido el algoritmo de clasificación estándar de Python desde la versión 2.3

Answer 2

Ellos son stable .

Por cierto: a veces puede ignorar saber si sort y sorted son estables, al combinar una ordenación de múltiples pasos en una sola pasada.

Por ejemplo, si desea ordenar objetos en función de sus last_name , first_name , puede hacerlo en una sola pasada:

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

aprovechando la comparación de tuplas.

Esta respuesta, tal como está, cubre la pregunta original. Para más preguntas relacionadas con la clasificación, existe la stable .

Answer 3

La documentación cambió mientras tanto ( confirmación pertinente ) y la documentación actual de sorted lo garantiza explícitamente:

La función incorporada sorted() está garantizada para ser 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).

Esta parte de la documentación se agregó a Python 2.7 y Python 3.4 (+) por lo que cualquier implementación compatible de esa versión de idioma debería tener una sorted estable.

Tenga en cuenta que para CPython el list.sort ha sido estable desde Python 2.3

• Tim Peters reescribió su implementación de list.sort() : esta es una "clasificación estable" (las entradas iguales aparecen en el mismo orden en la salida) y más rápido que antes.

No estoy 100% seguro en sorted , hoy en día es simple usa list.sort , pero no he revisado el historial para eso. Pero es probable que "siempre" use list.sort .

Answer 4

Los documentos "Novedades" para Python 2.4 hacen que el hecho de que sorted () primero cree una lista, luego llame 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.

Answer 5

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