Modulo 14 - Metodos de ordenação

Prévia do material em texto

© E.L.Favero Algoritmos em Python 97 
 
 
 
 
Capítulo 
 
14 MÉTODOS DE ORDENAÇÃO 
Iniciamos com a apresentação de passagem de parâmetros por referência. Mostramos 
alguns métodos de ordenação de listas, como uma forma de exercitar o 
desenvolvimento de algoritmos e as técnicas de programação. 
 
 
 
14.1 Passagem de parâmetros por referência 
 
Python tem dois tipos de passagem de parâmetros para uma função, por valor ou por 
referência. 
 Passagem por valor: uma variável do tipo imutável (int, float, bool, char, string, 
tupla) é passada por valor. Uma cópia do valor e levada para dentro da função. Até agora 
sempre usamos parâmetros passados por valor. No exemplo abaixo, uma tentativa de troca, 
a função trocaAB() não afeta os valores x e y, que continuam com 2 e 5. 
 
def trocaAB(a,b): 
 a,b=b,a 
 return 
x=2;y=5; 
trocaAB(x,y); 
print(x,y) 
>>> 
2 5 
 
Abaixo temos uma função que troca dois elementos de um vetor. A troca pode ser feita com 
atribuição múltipla ou com o uso de uma variável temporária. Para que a função troca() 
deixe efeito no vetor precisamos do conceito de passagem de parâmetro por referência. 
 
# troca dois elementos de um vetor v, índices a,b 
def troca(v, a, b ): 
 #----(out,in,in) 
 v[a],v[b]=v[b],v[a] 
 return 
v1=[1,7,9,12] 
print(v1) 
troca(v1,1,3) 
print(v1) 
>>> 
 © E.L.Favero Algoritmos em Python 98 
 
 
[1, 7, 9, 12] 
[1, 12, 9, 7] 
 
 
# troca dois elementos de um vetor v, índices a,b 
def troca1(v,a,b): 
 temp=v[a];v[a]=v[b];v[b]=temp 
 return 
 
 
 
Fonte: Python Tutor 
 
 
Passagem por referência: uma variável do tipo mutável (listas e dicionários) é passada por 
referência. Na função troca() o parâmetro formal v é substituído por uma referencia ao vetor 
v1; assim ambos v e v1 referenciam o mesmo vetor. Com isso o efeito da troca fica 
permanente em v1. Neste caso v1 entra e sai da função troca. Na troca() temos um return 
vazio, pois o efeito da troca acontece sobre o vetor v1 – pode-se escrever também return 
None. 
 
 
BOX1: Em algumas linguagens de programação existe uma diferença entre uma 
função e procedimento. A função recebe parâmetros e retorna valores encima de 
seu nome, para ser utilizada dentro de uma expressão, por exemplo, num 
comando de atribuição. Um procedimento deixa o seu efeito sobre variáveis ou 
estruturas de dados como no exemplo da troca, sem retorno de valor sobre seu 
nome. Um procedimento pode ser chamado como um comando qualquer fora de 
uma expressão. 
 
 
 
 
 
 
 
14.2 Ordenção: método da bolha 
 
Agora compreendendo como se trocam dois elementos de um vetor podemos fazer um dos 
métodos de ordenação chamado bubble sort ou método da bolha. Este método consiste 
em testar dois elementos contíguos de um vetor, se V[i]>V[i+1] então troca-se o conteúdo 
destas duas posições. Varrendo-se o vetor do início até o fim sempre fazendo estas trocas 
 © E.L.Favero Algoritmos em Python 99 
 
 
aos poucos os valores maiores vão para o final e os menores ficam no início. Quando é 
possível percorrer o vetor e não for feita nelhuma troca então o processo termina pois o 
vetor está totalmente ordenado. 
 
def bolhaOrd(V): 
 trocaOK=True 
 while trocaOK: 
 trocaOK=False 
 for i in range(len(V)-1): 
 if V[i]>V[i+1]: 
 V[i],V[i+1]=V[i+1],V[i]; 
 trocaOK=True 
 return V 
S1='blagla'; 
V=list(S1) 
print(''.join(bolhaOrd(V))) 
 
Rodando o método da bolha sobre a lista “blagla” a primeira troca será das letras “la” por 
“al”, como ilustrado abaixo no python tutor, ficando “balgal”; depois “lg” por “gl”, etc. 
 
 
 
 
 
 © E.L.Favero Algoritmos em Python 100 
 
 
 
 
Na primeira passagem sobre a lista toda o l que estava na segunda posição vai sendo 
levado para a 5 posição. No total são 88 passos (ver abaixo). No passo 61 a lista tá quase 
ordenada, só falta uma troca. 
 
Troca Novo string 
1 blagla 
2 balgla 
3 baglla 
4 baglal 
 
 
 
 
 
14.3 Ordenação: Seleçao direta 
Outro método de ordenação fácil de compreender é a seleção direta. Usando a função 
troca() e a função que retorna o índice do elemento máximo do vetor, imax1(), podemos 
fazer um algoritmo de ordenação: que traz sempre o máximo para o início da lista final, com 
sucessivas trocas. 
 Note que a troca() e a ordena() destrõem o vetor original. Portanto, para testar as 
diferentes versões com a mesma entrada devemos tirar uma cópia do vetor para preservá-
lo, com V1=list(V) ou V1=V[:]. 
 
 
 
 
 
 © E.L.Favero Algoritmos em Python 101 
 
 
# ordena, usando imax1(j,V) e troca(), 
# trazendo sempre o máximo para o início 
def ordena(v): 
 for i in range(len(v)): 
 m=imax1(i,v) 
 v[m],v[i]=v[i],v[m] 
 return(v) 
def ordena1(v): 
 for i in range(len(v)):m=imax1(i,v);troca(v,i,m) 
 return v 
def ordena2(v): 
 for i in range(len(v)):troca(v,i,imax1(i,v)) 
 return v 
 
print('troca 3 x 4:',troca(V,3,4)) 
V=[1,3,7,11,23,6] 
V1=list(V) # copia da lista V 
V2=V[:] # idem, copia a lista V 
V3=V[:] 
print(' ordena:', ordena(V1)) 
print('ordena1:', ordena1(V2)) 
print('ordena2:', ordena2(V3)) 
 
Nas versõe acima, usamos a estratégia de manipular os elementos do vetor de entrada. 
Sistematicamente troca-se o máximo pela ponta da lista ordenada. 
 Agora vamos destruir a lista de entrada, com del de elementos, e construir outra 
para a a saída, o retorno. Em Python existe a função del V[i] que deleta o elemento i de V. 
Podemos fazer uma função ordenad() que pega o imax(), deleta-o, e coloca ele noutra lista 
aux, criando uma nova lista ordenada. 
 
 
 
 © E.L.Favero Algoritmos em Python 102 
 
 
 
 
 
Nas execuções acima, podemos ver lista aux(iliar) sendo criada: a cada passo o max é 
removido de v e adicionado em aux. Nesta versão usamos as funções max() e index() do 
Python. 
 
def imax(v): 
 M=0; 
 for i in range(1,len(v)): 
 if v[M]<v[i]:M=i 
 return M 
def ordenad(v): 
 aux=[] 
 while v!=[]: 
 m=imax(v); aux.append(v[m]); del v[m] 
 return aux 
def ordenad1(v): 
 aux=[] 
 while v!=[]: 
 m=v.index(max(v)); aux.append(v[m]); del v[m] 
 return aux 
 
V=[1,3,7,11,23,6] 
V1=V[:];V2=V[:] 
print(' ordenad:', ordenad(V1)) 
print('ordenad1:', ordenad1(V2)) 
 
Existe uma pequena diferença entre ordenad() e ordenad1(). Podemos pensar que a 
primeira é um pouco mais eficiente, pois quando encontrou o máximo já memorizou o índice 
e a segunda depois de encontrar o máximo ainda busca o índice v.index(). 
 
 
 
 
 
 
 
 
 
 © E.L.Favero Algoritmos em Python 103 
 
 
14.4 Exercícios (7) 
Ao responder estes exercícios, teste cada função com uma entrada para garantir que a 
saída está correta. 
 
E14.1 Defina a função troca, que troca dois elementos de um vetor v, índices a,b com 
atribuição múltipla 
def troca(v,a,b): 
 v[a],v[b]=v[b],v[a] 
 return 
 
E14.2 Defina a função que troca dois elementos de um vetor v, índices a,b usando uma 
variável temporária 
 
E14.3 Defina o método de ordenação da bolha para um vetor 
 
E14.4 Defina o método de ordenação por seleção direta, usando imax1(j,V) e fazendo troca 
com atribuição múltipla; trazendo sempre o máximo para o início da lista sendo 
ordenada 
def imax1(j,v): 
 M=j; 
 for i in range(j,len(v)): 
 if v[M]<v[i]:M=i 
 return M 
V=[3,6,9,1,1,3,8]; print(' imax:', imax1(3,V)) 
 
def ordena(v): 
 for i in range(len(v)): 
 m=imax1(i,v) 
 v[m],v[i]=v[i],v[m] 
 return(v) 
V=[1,3,7,11,23,6];V1=list(V) 
print(' ordena:', ordena(V1)) 
 
E14.5 Defina o método de ordenação por seleção direta, usando imax1(j,V) e troca() 
 
E14.6 Faça a função ordenad() que pega o imax(), deleta-o, e coloca ele noutra lista aux, 
que monta a nova listaordenada. 
 
def imax(v): 
 M=0; 
 for i in range(1,len(v)): 
 if v[M]<v[i]:M=i 
 return M 
def ordenad(v): 
 aux=[] 
 while v!=[]: 
 m=imax(v); aux.append(v[m]); del v[m] 
 return aux 
 
E14.7 Faça a função de seleção direta, de ordenação, ordenad1() usando max() e index() 
primitivas do Python 
def ordenad1(v): 
 aux=[] 
 while v!=[]: 
 m=v.index(max(v));aux.append(v[m]); del v[m] 
 © E.L.Favero Algoritmos em Python 104 
 
 
 return aux 
V=[1,3,7,11,23,6];V2=V[:] 
print('ordenad1:', ordenad1(V2)) 
 
 
 
 
 
14.4.1 Perguntas conceituais (1) 
 
 Responda com no mínimo 10 palavras e no máximo 20 palavras: 
C14.2 Como podemos duplicar, ou tirar uma cópia de uma lista? 
C14.3 Como funciona passagem de parâmetro por valor? 
C14.4 Como funciona passagem de parâmetro por referência? 
 
Projeto Nerd (avançado *complexo). Crie um vetor aleatório, de randint(), com tamanho 
1000 (ver próximo capítulo sobre matrizes). Usando os recursos de tempo, import time, 
como ilustrado abaixo, compare o tempo das funções de ordenação. Qual delas é mais 
rápida? 
 
import time as t 
def miliseg(): return t.time()*1000 
t0 = miliseg() # inicia a contagem do tempo 
for i in range(100000): 
 x=10+10 
t1 = miliseg() #fim da contagem de tempo 
print(round((t1-t0),4),"miliseg para fazer 100k somas") 
>>> 
31.2366 miliseg para fazer 100k somas