HOW TO - Ordenar

Autor:

Andrew Dalke and Raymond Hettinger

Versión:

0.1

Las listas de Python tienen un método incorporado list.sort() que modifica la lista in situ. También hay una función incorporada sorted() que crea una nueva lista ordenada a partir de un iterable.

En este documento exploramos las distintas técnicas para ordenar datos usando Python.

Conceptos básicos de ordenación

Una clasificación ascendente simple es muy fácil: simplemente llame a la función sorted(). Retorna una nueva lista ordenada:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

También puede usar el método list.sort(). Modifica la lista in situ (y retorna None para evitar confusiones). Por lo general, es menos conveniente que sorted(), pero si no necesita la lista original, es un poco más eficiente.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

Otra diferencia es que el método list.sort() solo aplica para las listas. En contraste, la función sorted() acepta cualquier iterable.

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Funciones clave

Ambos list.sort() y sorted() tienen un parámetro key para especificar una función (u otra invocable) que se llamará en cada elemento de la lista antes de hacer comparaciones.

Por ejemplo, aquí hay una comparación de cadenas que no distingue entre mayúsculas y minúsculas:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

El valor del parámetro key debe ser una función (u otra invocable) que tome un solo argumento y retorne una clave para usar con fines de clasificación. Esta técnica es rápida porque la función de la tecla se llama exactamente una vez para cada registro de entrada.

Un uso frecuente es ordenar objetos complejos utilizando algunos de los índices del objeto como claves. Por ejemplo:

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

La misma técnica funciona para objetos con atributos nombrados. Por ejemplo:

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Funciones del módulo operator

Las funciones clave utilizadas anteriormente son muy comunes, por lo que Python proporciona funciones para facilitar y agilizar el uso de las funciones de acceso. El módulo operator contiene las funciones itemgetter(), attrgetter(), y methodcaller().

Usando esas funciones, los ejemplos anteriores se vuelven más simples y rápidos:

>>> from operator import itemgetter, attrgetter

>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Las funciones del módulo operator permiten múltiples niveles de clasificación. Por ejemplo, para ordenar por grade y luego por age:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

Ascendente y descendente

Ambos list.sort() y sorted() aceptan un parámetro reverse con un valor booleano. Esto se usa para marcar tipos descendentes. Por ejemplo, para obtener los datos de los estudiantes en orden inverso de edad:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Estabilidad de ordenamiento y ordenamientos complejos

Se garantiza que las clasificaciones serán estables. Eso significa que cuando varios registros tienen la misma clave, se conserva su orden original.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Observe cómo los dos registros para blue conservan su orden original de modo que se garantice que ('blue', 1) preceda a ('blue', 2).

Esta maravillosa propiedad le permite construir ordenamientos complejos en varias etapas. Por ejemplo, para ordenar los datos de estudiantes en orden descendente por grade y luego ascendente por age, ordene primero por age y luego por grade:

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Esto se puede encapsular en una función que tome una lista y tuplas (atributo, orden) para ordenarlas por múltiples pases.

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

El algoritmo Timsort utilizado en Python realiza múltiples ordenamientos de manera eficiente porque puede aprovechar cualquier orden ya presente en el conjunto de datos.

Decorate-Sort-Undecorate

Este patrón de implementación, llamado DSU (por sus siglas en inglés Decorate-Sort-Undecorate), se realiza en tres pasos:

• Primero, la lista inicial está «decorada» con nuevos valores que controlarán el orden en que se realizará el pedido.

• En segundo lugar, se ordena la lista decorada.

• Finalmente, los valores decorados se eliminan, creando una lista que contiene solo los valores iniciales en el nuevo orden.

Por ejemplo, para ordenar los datos de los estudiantes por grade utilizando el enfoque DSU:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Esta técnica funciona porque las tuplas se comparan en orden lexicográfico; se comparan los primeros objetos; si hay objetos idénticos, se compara el siguiente objeto, y así sucesivamente.

No es estrictamente necesario en todos los casos incluir el índice i en la lista decorada, pero incluirlo ofrece dos ventajas:

• El orden es estable: si dos elementos tienen la misma clave, su orden se conservará en la lista ordenada.

• Los elementos originales no tienen que ser comparables porque el orden de las tuplas decoradas estará determinado por, como máximo, los dos primeros elementos. Entonces, por ejemplo, la lista original podría contener números complejos que no se pueden ordenar directamente.

Otro nombre para esta técnica es Transformación Schwartziana, después de que Randal L. Schwartz la popularizara entre los programadores de Perl.

Ahora que la clasificación de Python proporciona funciones clave, esta técnica ya no se usa con frecuencia.

Funciones de comparación

A diferencia de las funciones clave que devuelven un valor absoluto para la ordenación, una función de comparación calcula la ordenación relativa para dos entradas.

Por ejemplo, una escala de balance compara dos muestras dando un orden relativo: más ligero, igual o más pesado. Del mismo modo, una función de comparación como cmp(a, b) devolverá un valor negativo para menor que, cero si las entradas son iguales, o un valor positivo para mayor que.

Es habitual encontrar funciones de comparación al traducir algoritmos de otros lenguajes. Además, algunas bibliotecas proporcionan funciones de comparación como parte de su API. Por ejemplo, locale.strcoll() es una función de comparación.

Para adaptarse a estas situaciones, Python proporciona functools.cmp_to_key para envolver la función de comparación y hacerla utilizable como una función clave:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Curiosidades

• Para ordenar teniendo en cuenta la localización, utilice locale.strxfrm() para una función clave o locale.strcoll() para una función de comparación. Esto es necesario porque la ordenación «alfabética» puede variar entre culturas aunque el alfabeto subyacente sea el mismo.

• El parámetro reverse aún mantiene estabilidad de ordenamiento (de modo que los registros con claves iguales conservan el orden original). Curiosamente, ese efecto se puede simular sin el parámetro utilizando la función incorporada reversed() dos veces:

  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
  >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
  >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
  >>> assert standard_way == double_reversed
  >>> standard_way
  [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
  

• The sort routines use < when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method:

  >>> Student.__lt__ = lambda self, other: self.age < other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

  However, note that < can fall back to using __gt__() if __lt__() is not implemented (see object.__lt__()).

• Las funciones clave no necesitan depender directamente de los objetos que se ordenan. Una función clave también puede acceder a recursos externos. Por ejemplo, si las calificaciones de los estudiantes se almacenan en un diccionario, se pueden usar para ordenar una lista separada de nombres de estudiantes:

  >>> students = ['dave', 'john', 'jane']
  >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
  >>> sorted(students, key=newgrades.__getitem__)
  ['jane', 'dave', 'john']