(actualizado em 18 de Outubro de 2018)
Ordenar valores é uma actividade particularmente importante, que tem sido objecto de aturado estudo em ciência da computação. Não é por acaso que, em francês, o computador se denomina ordinateur.
Sendo uma actividade quotidiana para o humano, na manipulação de pequenas quantidades de informação, a qualidade dos algoritmos de ordenação utilizados torna-se especialmente relevante quando lidamos, mecanicamente, com grandes quantidades de informação.
A pesquisa de valores numa lista ordenada é particularmente eficiente. Atente-se por exemplo no seguinte programa, que implementa a chamada pesquisa binária de um elemento x numa lista ordenada (por ordem crescente) w, devolvendo (um)a posição em que o elemento surge na lista, ou False caso o elemento não ocorra. É fácil de verificar que o número de comparações efectuado pelo algoritmo é da ordem de $\log_2(n)$ para uma lista com $n$ elementos.
def binsearch(x,w):
found=False
left=0
right=len(w)-1
while not(found) and left<=right:
mid=(left+right)//2
if x==w[mid]:
found=True
elif x<w[mid]:
right=mid-1
else:
left=mid+1
if found:
return mid
else:
return False
w=list(range(1000))
%time binsearch(999,w)
w=list(range(2000))
%time binsearch(1999,w)
w=list(range(4000))
%time binsearch(3999,w)
w=list(range(8000))
%time binsearch(7999,w)
Naturalmente, como já vimos, a linguagem Python oferece a função predefinida sorted e também o método sort do tipo lista, para ordenar listas de valores (ou outros objectos iteráveis). É útil, no entanto, ignorar a sua existência por forma a compreendermos a algoritmia por detrás da ordenação. Vamos assim percorrer, passo a passo, alguns dos algoritmos de ordenação mais populares.
Vamos ordenar listas de números por ordem crescente, mas é óbvio que os mesmos algoritmos se podem aplicar à ordenação de outros valores usando uma relação de ordem adequada.
Os primeiros algoritmos de ordenação que analisaremos, particularmente ineficientes, exploram o facto de que alguma permutação dos elementos dados terá de estar ordenada.
Se percorrermos todas as permutações dos elementos (para $n$ elementos haverá $n!$ permutações a considerar), basta obviamente ir testando se estão ou não ordenadas.
def permutacoes(w):
res=[[]]
for x in w:
nres=[]
for u in res:
for i in range(len(u)+1):
novo=u[:]
novo.insert(i,x)
nres+=[novo]
res=nres
return res
def ordQ(w):
i=1
ok=True
while ok and i<len(w):
if w[i]<w[i-1]:
ok=False
else:
i=i+1
return ok
def slowsort(w):
poss=permutacoes(w)
i=0
while not ordQ(poss[i]):
i=i+1
return poss[i]
Repescamos a definição de permutacoes desenvolvida anteriormente, definimos o predicado auxiliar ordQ, e usamo-lo para definir a função permutsort desejada. Atente-se no facto de ser particularmente ineficiente, mesmo para listas de valores de tamanho modesto, o que explica a designação slow sort. No pior caso, o algoritmo calcula o resultado em tempo proporcional a $n!$ para uma lista de valores com $n$ elementos.
Para testar experimentalmente este e outros algoritmos vamos tirar partido da possibilidade de gerar permutações (pseudo-)aleatórias de uma certa lista de valores, importando o módulo random.
from random import *
w=list(range(20))
shuffle(w)
%time slowsort(w)
Na verdade é até instrutivo definirmos a nossa própria versão de shuffle, recorrendo à função randrange cujo significado é óbvio.
def shufflecaseiro(w):
for i in range(len(w)):
j=randrange(i,len(w))
w[i],w[j]=w[j],w[i]
return w
shufflecaseiro(list(range(10)))
shufflecaseiro(list(range(10)))
Neste contexto, podemos também explorar aleatoriamente as possíveis permutações da lista dada. Dessa forma obtemos um algoritmo probabilístico em que com sorte (muito baixa probabilidade) podemos conseguir obter o resultado desejado mais rapidamente, mas em que com azar podemos ter de esperar ainda mais do que com slow sort.
def luckysort(w):
while not(ordQ(w)):
shufflecaseiro(w)
return w
%time luckysort(shufflecaseiro(list(range(10))))
%time luckysort(shufflecaseiro(list(range(10))))
Mais adiante teremos ocasião de voltar a falar de algoritmos aleatórios, mas vale a pena notar que se trata de um tópico muito importante em algoritmia e aplicações à engenharia, que é alvo de estudo de diversas disciplinas mais avançadas.
Considerando agora algoritmos de facto relevantes, os mais simples que conseguimos conceber e mesmo executar manualmente, usam tempo quadrático no número de elementos a ordenar. No pior caso, o resultado é calculado em tempo proporcional a $n^2$ para uma lista de valores com $n$ elementos.
Há essencialmente duas opções, duais entre si. Colocar o esforço na pesquisa de elementos na lista dada, ou na sua colocação na lista ordenada.
Na ordenação por inserção, os valores dados são percorridos sequencialmente. A lista ordenada vai sendo construída, passo a passo, inserindo correctamente cada elemento entre os restantes já avaliados por forma a manter a ordenação. O esforço é colocado na inserção.
def insere(x,w):
i=0
while i<len(w) and w[i]<x:
i=i+1
w.insert(i,x)
return w
def insertsort(w):
res=[]
for i in range(len(w)):
insere(w[i],res)
return res
%time insertsort(shufflecaseiro(list(range(10))))
%time insertsort(shufflecaseiro(list(range(100))));None
%time insertsort(shufflecaseiro(list(range(1000))));None
É útil e ilustrativo, até para fins de comparação com os algoritmos seguintes, observar o seguinte filme que ilustra o funcionamento do algoritmo de ordenação por inserção para uma permutação aleatória dos números até 200.
from IPython.display import HTML
HTML("""
<video width="400" height="400" controls>
<source src="insertionsort.mp4" type="video/mp4">
</video>
""")
## video exportado do sistema Mathematica em formato swf e convertido depois para mp4
Note-se ainda que o algoritmo de ordenação por inserção é particularmente adequado para situações em que os valores a ordenar são recebidos sequencialmente, em vez de todos de uma vez.
Na ordenação por selecção, por oposição à ordenação por inserção, o custo associado está ligado à escolha do elemento a colocar na lista ordenada e não à colocação propriamente dita. À lista ordenada vai-se adicionando, sucessivamente, o valor mínimo ainda por analisar. O esforço é portanto colocado na selecção do mínimo.
def posmin(w,pos):
for i in range(pos+1,len(w)):
if w[i]<w[pos]:
pos=i
return pos
def selectsort(w):
for i in range(len(w)-1):
j=posmin(w,i)
if j!=i:
x=w.pop(j)
w.insert(i,x)
return w
Vale a pena notar que a lista é ordenada in situ, não sendo necessário trabalhar com um nome para ir armazenando resultados intermédios. Em cada momento, a lista ordenada dos elementos já processados é formada pelos primeiros i elementos de w.
%time selectsort(shufflecaseiro(list(range(10))))
%time selectsort(shufflecaseiro(list(range(100))));None
%time selectsort(shufflecaseiro(list(range(1000))));None
Vale a pena comparar, e notar as diferenças, entre o filme que usámos para ilustrar a ordenação por inserção e o filme seguinte, que ilustra o funcionamento do algoritmo de ordenação por selecção também para uma permutação aleatória dos números até 200.
HTML("""
<video width="400" height="400" controls>
<source src="selectionsort.mp4" type="video/mp4">
</video>
""")
## video exportado do sistema Mathematica em formato swf e convertido depois para mp4
Os algoritmos de ordenação gerais mais eficientes são utilizados em inúmeras situações e usam, em média, tempo quase-linear no número de elementos a ordenar, isto é, o resultado é calculado em tempo proporcional a $n.\log(n)$ para uma lista de valores com $n$ elementos.
Mais uma vez há duas versões, duais entre si. A ideia básica consiste em, a cada passo, dividir a lista de elementos a ordenar em duas listas com metade dos elementos. Num caso, partiremos a lista ao meio, ordenando ambas, e construindo depois a fusão das duas sublistas. No outro caso colocamos o esforço na escolha das sublistas, que depois de ordenadas precisam apenas de ser concatenadas.
O algoritmo de Hoare (desenvolvido pelo cientista britânico Tony Hoare), ou quick sort, coloca o esforço na escolha das sublistas. Por simplicidade toma-se o primeiro elemento da lista, $x$ e constroem-se duas sublistas com os elementos menores ou iguais a $x$ numa delas, e os elementos maiores que $x$ na outra. Na situação ideal, as duas sublistas terão sensivelmente metade dos elementos.
def split(w):
x=w[0]
left=[]
right=[]
for i in range(1,len(w)):
if w[i]<=x:
left+=[w[i]]
else:
right+=[w[i]]
return left,x,right
def quicksort(w):
if len(w)<2:
return w
else:
w1,x,w2=split(w)
return quicksort(w1)+[x]+quicksort(w2)
A definição de quicksort é um exemplo paradigmático em que é de facto mais conveniente usar recursão. Veremos mais tarde como fazer uma definição estritamente imperativa.
Note-se, abaixo, como de facto há uma melhoria relativamente aos algoritmos anteriores, particularmente sensível para listas maiores.
%time quicksort(shufflecaseiro(list(range(10))))
%time quicksort(shufflecaseiro(list(range(100))));None
%time quicksort(shufflecaseiro(list(range(1000))));None
Como uma imagem, por vezes, vale mais do que mil palavras, o filme seguinte ilustra o funcionamento do algoritmo de Hoare na ordenação de uma permutação aleatória dos números até 200.
HTML("""
<video width="400" height="400" controls>
<source src="quicksort.mp4" type="video/mp4">
</video>
""")
## video exportado do sistema Mathematica em formato swf e convertido depois para mp4
Note-se que o algoritmo quicksort é ainda assim quadrático no pior caso (porquê?).
O algoritmo de ordenação por fusão, ou merge sort, é semelhante, mas coloca o esforço na junção das sublistas ordenadas. As sublistas resultam apenas de separar pelo meio a lista dada.
def fusao(u,v):
res=[]
i=0
j=0
for k in range(len(u)+len(v)):
if i<len(u) and (j==len(v) or u[i]<v[j]):
res.append(u[i])
i=i+1
else:
res.append(v[j])
j=j+1
return res
def mergesort(w):
if len(w)<2:
return w
else:
m=len(w)//2
w1=mergesort(w[:m])
w2=mergesort(w[m:])
return fusao(w1,w2)
%time mergesort(shufflecaseiro(list(range(10))))
%time mergesort(shufflecaseiro(list(range(100))));None
%time mergesort(shufflecaseiro(list(range(1000))));None
O filme seguinte ilustra o funcionamento do algoritmo merge sort durante a ordenação de uma permutação aleatória dos números até 200.
HTML("""
<video width="400" height="400" controls>
<source src="mergesort.mp4" type="video/mp4">
</video>
""")
## video exportado do sistema Mathematica em formato swf e convertido depois para mp4
Vale a pena notar que o algoritmo mergesort é genuinamente quase-linear, mesmo no pior caso.
Os algoritmos que vimos acima são os mais eficientes de entre os algoritmos de ordenação gerais. Mas, em certas situações específicas, poderá haver algoritmos mais eficientes, nomeadamente de tempo linear, isto é, tempo proporcional a $n$ para uma lista de valores com $n$ elementos.
Uma situação típica, que dá origem a diversos algoritmos variantes, acontece quando sabemos que os valores a ordenar pertencem todos a um certo conjunto finito.
(A versão que se implementa de seguida d)o algoritmo de contagem pressupõe que todos os valores da lista a ordenar são inteiros entre a e b (com a<b, claro).
def countsort(w,a,b):
space=range(a,b+1)
cont=[0 for val in space]
for i in range(len(w)):
cont[w[i]-a]+=1
res=[]
for val in space:
res+=[val for quant in range(cont[val-a])]
return res
%time countsort(shufflecaseiro(list(range(10))),0,10)
%time countsort(shufflecaseiro(list(range(100))),0,100);None
%time countsort(shufflecaseiro(list(range(1000))),0,1000);None
Note-se a acentuada melhoria relativamente a todos os algoritmos anteriores para listas maiores.
Para terminar, vale a pena recordar que nenhuma implementação que façamos se aproximará facilmente das primitivas predefinidas do Python.
%time sorted(shufflecaseiro(list(range(1000))));None
%time shufflecaseiro(list(range(1000))).sort()
Introdução à Programação em Mathematica (3a edição): J. Carmo, A. Sernadas, C. Sernadas, F. M. Dionísio, C. Caleiro, IST Press, 2014.
Think Python: How to think like a computer scientist: A. Downey, Green Tea Press, 2012.
Introduction to Computation and Programming Using Python (revised and expanded edition): J. V. Guttag, MIT Press, 2013.
The Art of Computer Programming: D. E. Knuth, Addison-Wesley (volumes 1--3, 4A), 1998.
Learning Python (fifth edition): M. Lutz, O'Reilly Media, 2013.
Programação em Python: Introdução à programação utilizando múltiplos paradigmas: J. P. Martins, IST Press, 2015.
Introdução à Programação em MatLab: J. Ramos, A. Sernadas e P. Mateus, DMIST, 2005.
Learning IPython for Interactive Computing and Data Visualization: C. Rossant, Packt Publishing, 2013.
Programação em Mathematica: A. Sernadas, C. Sernadas e J. Ramos, DMIST, 2003.