Ordenando listas no python2.3 e inferiores

Ordenação simples

Um objeto to tipo 'list' possui um método chamado 'sort' que faz a ordenação 'in-place' (resultado na própria variável) do objeto.

Descrição do método:

L.sort([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1'

Exemplo:

>>> lista = ['a', 'c', 'b']
>>> lista.sort()
>>> lista
['a', 'b', 'c']
>>>


Ordenação simples inversa

Para ordenar uma lista do maior para o menor item temos o método 'reverse', que trabalha de maneira análoga ao método 'sort'.

Exemplo:

>>> lista.reverse()
>>> lista
['c', 'b', 'a']
>>>

Ordenação de lista de dicionários por uma chave

O metodo 'sort' aceita uma função de comparação como paramêtro. Essa função caso seja informada será utilizada para comparar os itens da lista e resolver qual item prioridade na ordem sobre os demais.

Para que o método ordene a lista se baseando na chave dos dicionários a função criada sobrescreve a função 'bulti-in' 'cmp' do python.

A função 'cmp' como podemos ver abaixo, compara dois objetos recebidos como paramêtro retornando um inteiro que informa qual dos itens é maior ou se os dois são iguais. Baseado no resultado da função 'cmp' a função 'sort' ira ordenar a lista.

Descrição do método:

'cmp(x, y) -> integer\n\nReturn negative if xy.'

Em nosso exemplo desejamos ordenar a lista utilizando como base a chave (coluna) '2' do dicionário e assim a definimos.

Quando a função 'sort' estiver interando sobre a lista, ela vai passar cada item encontrado para a nossa função sort modificada 'mycmp' que por sua vez irá chamar a funcao 'cmp' passando como paramêtro o valor das chaves no dicionário pelo qual desejamos ordenar.

>>> lista = [{1: 'b', '2': 'b'}, {1: 'c', '2': 'a'}]
>>>
... def mycmp(a, b):
... print a
... print b
... return cmp(a.get('2'), b.get('2'))
...
>>> lista.sort(mycmp)
>>> lista
[{1: 'b', '2': 'b'}, {1: 'c', '2': 'a'}]

Também podemos utilizar 'lambda' para criar uma função anônima. O resultado é o mesmo, talvez com alguma variação de performance.

lista.sort(lambda x,y: cmp(a.get('2'), b('2')))

Ordenar listas de dicionários de acordo com uma ou mais chaves escolhidas

A função abaixo recebe dois paramêtros, a lista que se deseja ordenar e a lista de chaves que devem ditar a ordenação.

>>> lista = [{1: 1, '2': 'b', '3': 0}, {1: 1, '2': 'a', '3': -1}, {1: 0, '2': 'd', '3': 5}]
>>> def sort_list(l, sort_keys):
... def mycmp(a, b):
... k1 = map(lambda x: a.get(x), sort_keys)
... k2 = map(lambda x: b.get(x), sort_keys)
... return cmp(k1, k2)
...
... l.sort(mycmp)
... return l
...
>>> sort_list('1', lista, ['2', '1'])
[{1: 1, '3': -1, '2': 'a'}, {1: 1, '3': 0, '2': 'b'}, {1: 0, '3': 5, '2': 'd'}]

Criamos uma função 'closure' chamada 'mycmp', que como no exemplo anterior será passada para a função 'sort'. Dentro da funcao 'mycmp' é onde temos a diferença básica em relacao a função anterior. Ao invés de dizer qual o resultado de cada dicionário que ele deve utilizar para ordenar, passamos duas listas com os valores das colunas pelas quais desejamos ordenar.

Novamente, o 'sort' utlizando a funcao 'cmp' irá decidir qual dos dois objetos deve ter a preferência e assim ordenar a lista de dicionários de acordo com as colunas que especificamos.

Atenção, alguns módulos como por exemplo 'mxDatetime' sobrescrevem o método sort para que funcionem a seu gosto. Isso pode fazer com o que o método 'cmp' que estiver no namespace local não seja o 'cmp' original, caso você utilize algum módulo onde isso acontece o sort não irá funcionar corretamente. Neste caso deveremos importar a função 'cmp' diretamente das funções 'bulti-in' ou melhor do namespace '__builtin__'.

Detalhe sobre a implementação do método sort

O algoritmo de 'sort' utilizado no python é um tando diferente dos algoritmos tradicionais, um tipo de mergesort com algumas coisas a mais.

Retirado dos fontes do python listsort.txt:

"This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency."