 |
 |
 |
|
| Sempre idente seus códigos. Isso facilita a manutenção e fica bonito. |
|
|
Algoritmos de ordenação - Parte 3: o mergesort
 Enviado por thotypous em Seg, 10/07/2006 - 11:02. Python
Continuando a série sobre algoritmos de ordenação, tratamos do mergesort, um algoritmo de ordenação recursivo que roda em tempo O(n log(n)). Explicaremos o algoritmo e daremos um exemplo de implementação em Python.
O mergesort
A essência do mergesort está no "juntar" (daí o nome "merge"). A idéia central do algoritmo se baseia na facilidade que temos para juntar dois vetores ordenados de forma que o vetor resultante também esteja ordenado.
Considere os vetores [1,3,6,7] e [1,2,4,5,8]. Note que ambos já estão ordenados. Uma forma de juntá-los mantendo a ordenação é percorrendo cada um da esquerda para a direita com o auxílio de dois marcadores de posição. Acrescentamos no vetor resultante o menor dos dois números que estão apontados pelos marcadores, e então deslocamos uma posição para a direita o marcador que estava apontando para ele. Fazemos isso até um dos vetores acabarem. Se sobrarem elementos no final do outro vetor, acrescentamos esses elementos no final do vetor resultante.
Faremos agora o procedimento acima com os dois vetores de exemplo. As letras "v" representarão setas que indicam os marcadores.
v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3,4] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3,4,5] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3,4,5,6] v Vetor 1: [1,3,6,7] v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3,4,5,6,7] Vetor 1: Varrido por completo v Vetor 2: [1,2,4,5,8] Resultado: [1,1,2,3,4,5,6,7,8]
Agora sabemos juntar dois vetores ordenados com apenas uma "passada" sobre eles, ou seja, tempo que esse procedimento toma para ser executado é linear com o número n de elementos do vetor resultante. Dizemos que esse procedimento tem tempo de execução O(n).
Podemos nos aproveitar dessa forma rápida de juntar dois vetores ordenados para criar um algoritmo de ordenação. Dividimos o vetor que queremos ordenar no meio e ordenamos cada metade. Depois usamos o procedimento acima para juntar as duas metades ordenadas.
Esse procedimento será recursivo. A cada recursão, o tamanho dos vetores a serem ordenados vai diminuindo pela metade. Uma hora teremos que parar essa recursão, tratando de um caso conhecido, o caso no qual o vetor que recebemos tem apenas um elemento. Neste caso, o vetor que recebemos já é ordenado, pois tem apenas um elemento, então paramos a recursão retornando o próprio vetor.
Tomando como exemplo o vetor [4,5,2,1,3,7,5], a árvore de recursão seria a seguinte:
[4,5,2,1,3,7,5] / \ [4,5,2,1] [3,7,5] / \ / \ [4,5] [2,1] [3,7] [5] / \ / \ / \ [4][5] [2][1] [3][7]
Note que paramos de construir a árvore quando o vetor fica com apenas um elemento. Chamamos esse critério de "critério de parada" da recursão.
Executando o procedimento descrito no começo deste artigo para juntar dois vetores ordenados, quando a recursão voltar, subiremos na árvore ordenando os vetores:
[1,2,3,4,5,5,7] / \ [1,2,4,5] [3,5,7] / \ / \ [4,5] [1,2] [3,7] [5] / \ / \ / \ [4][5] [2][1] [3][7]
E pronto, a ordenação está feita, como mágica! :D Algoritmos de recursão não são divertidos? :P
Note que o número de níveis de recursão é aproximadamente o logarítmo na base 2 do número de elementos do vetor que está sendo ordenado. O tempo total de execução para esse algoritmo fica, então, O(n log(n)).
A seguir, temos o exemplo de implementação em Python. Para não precisar ficar dividindo o vetor e passando outros vetores para os próximos níveis de recursão, passamos dois parâmetros (i e f), que são índices que indicam o começo e o fim do vetor que está sendo tratado:
def msort(a, i, f): if i == f: # critério de parada return [a[i]] # um vetor de um elemento é sempre ordenado elif i > f: # argumentos inválidos recebidos return [] # trata como se fosse um vetor vazio mid = (i + f) / 2 # divide o vetor no meio # ordenamos cada metade do vetor fazendo a chamada recursiva b = msort(a, i, mid) c = msort(a, mid+1, f) # procedimento descrito no texto para juntar dois vetores ordenados # j e k são os índices dos marcadores e v é o vetor resultante j = 0 k = 0 v = [] while (len(b) > j) and (len(c) > k): if c[k] > b[j]: v += [b[j]] j += 1 else: v += [c[k]] k += 1 # se sobrarem elementos em algum dos vetores, juntamos ao final do # vetor resultante. note que nunca sobrarão elementos nos dois vetores # ao mesmo tempo. v += b[j:len(b)] v += c[k:len(c)] return v # executamos um teste para o algoritmo a = [4,5,2,1,3,7,5] print repr(a) print repr(msort(a, 0, len(a)-1))
No próximo, e último, artigo da série, trataremos do quicksort, que tem tempo de execução médio O(n log(n)). O quicksort é mais eficiente que o mergesort pois não precisamos ficar juntando vetores, trabalhamos apenas com trocas, que é um procedimento mais rápido e que utiliza menos memória, pois trabalhamos sempre no mesmo vetor, sem criar vetores auxiliares.
Não perca quarta-feira o último artigo da série sobre Algoritmos de Ordenação, no qual trataremos sobre o quicksort!
|
  |
|
|
