8.1 Ordenando uma Lista

Também é útil que você entenda como ordenar seus dados sem

depender da linguagem, pois nem todas as linguagens de programação vão fornecer um mecanismo tão direto quanto Python. Apesar de Python ter esse mecanismo, você terá a vantagem de entender como isso pode ser feito internamente e quando se deparar com uma linguagem sem esse mecanismo embutido, poderá programar seu próprio método de ordenação.

 

8.1 ORDENANDO UMA LISTA

Um algoritmo muito simples de ordenação é o chamado “método da bolha”, muitas vezes chamado de bubblesort, da palavra em inglês. Este algoritmo é muito ineficiente e mostrarei como ordenar de maneira mais rápida no futuro. O algoritmo é simples e vai preparar você para outros algoritmos melhores. Aliás, em uma situação muito particular, esse algoritmo é o mais rápido que podemos escrever, mas vou deixar como curiosidade para o final da seção.

Vamos começar com uma prosa. A ideia básica do ordenamento

por borbulhamento consiste em comparar cada par de elementos consecutivos de uma lista de elementos e, sempre que descobrir que estão fora de ordem, trocá-los de posição, colocando o maior elemento após o menor. Da primeira vez que fazemos isso, a lista pode ainda não estar ordenada, mesmo tendo sido percorrida completamente, mas temos certeza de que o maior elemento estará na última posição da lista. Os itens “mais leves se movimentam para o início apenas uma posição por vez, mas o mais “pesado” vai direto para o fim.

 

Figura 8.1 Primeiro passo do algoritmo de ordenação por bolha.

Percorremos a lista uma segunda vez, comparando sempre os elementos consecutivos. Agora o segundo maior elemento estará na penúltima posição. Quantas vezes temos de repetir este processo para garantir que todos os elementos estejam na sua posição correta e que a lista está ordenada? Pense um pouco. A resposta não é difícil.

Começamos a formalizar nosso algoritmo, ainda como uma prosa:

Para ordenar uma lista de n elementos em ordem crescente, comparamos o primeiro elemento com o segundo. Se o primeiro for maior que o segundo, nós os trocamos de posição dentro da lista. Agora comparamos o segundo elemento com o terceiro, e novamente os trocamos de posição se descobrirmos que se encontram em ordem errada. Fazemos isso com cada par de elementos consecutivos, até compararmos o penúltimo com o último. Se executarmos este algoritmo n-1 vezes, nossa lista terá seus elementos ordenados em ordem crescente.

 

Por que n-1 vezes? Você já deve ter percebido, mas sempre é bom reforçar. Imagine que você tenha 10 elementos para ordenar. Se a cada passagem pela lista um elemento ficar obrigatoriamente na posição correta, em 9 passagens, você terá certeza de que 9 elementos estão ordenados, portanto o décimo também estará.

Outra forma de pensar é que se os elementos “leves” se deslocam apenas um lugar por vez, se o menor elemento estiver no final da lista, irá levar 9 passagens para chegar à sua posição correta. Chamamos essa situação de “pior caso” do algoritmo: a condição na qual o algoritmo tomará mais tempo para ser executado.

No algoritmo em questão, não existe na realidade nem melhor nem pior caso, pois foi fixado o número de vezes em que é executado, mas isso pode ser melhorado no futuro.

Agora vamos passar esta prosa para um algoritmo, seguindo

algumas formalidades. Começamos com uma ideia bem genérica da solução:

Seja uma lista com n elementos

Repita n-1 vezes

Percorrer a lista trocando elementos consecutivos

que estejam fora de ordem

Agora você deve pensar em como percorrer uma lista,

comparando os elementos. A forma mais simples é usar uma variável auxiliar, i, para ser um índice dos elementos da lista. Esse índice deve variar entre o primeiro e o penúltimo elemento. Como os índices começam em zero, o penúltimo elemento será o de índice n-2 . O trecho fica assim:

Para i variando entre 0 e n-2:

Se lista[i] > lista{i+1}

troque elementos de posição.

Nosso algoritmo fica:

Seja uma lista com n elementos

Repita n-1 vezes

Para i variando entre 0 e n-2:

Se lista[i] > lista[i+1]:

troque elementos de posição.

Temos agora um algoritmo suficientemente detalhado para

podermos converter em um programa. Sempre é bom começar com um algoritmo. Perceba os passos que segui. Comecei com uma ideia vaga, passei para uma prosa mais detalhada, em seguida escrevi um algoritmo ainda deixando partes vagas e fui refinando seus passos até chegar a algo que está bem próximo de uma linguagem de programação.

Agora vamos ver como podemos traduzir este algoritmo em

programa.

Primeiro, quero que este seja um programa genérico, que aceite

qualquer lista para ordenar. Dessa forma é lógico implementá-lo como uma função e a lista será passada como um argumento.

O valor de n poderia ser também passado como argumento da função, mas é mais interessante deixar o programa calcular para você este valor. Por isso, quando você quiser usar uma lista com diferentes elementos, não precisará saber de antemão quantos elementos a lista possui.

Para repetir um mesmo comando n-1 vezes, Python fornece o comando for. Temos apenas de gerar uma lista de n-1 elementos. Isso pode ser feito com o comando range(n-1). Lembre-se de que este comando vai gerar a lista [0,1,2,...,n-2] que possui n-1 elementos. Os valores não importam muito, desde que o comando tenha n-1 elementos.

O laço mais interno, que varia entre 0 e n-2 pode ser gerado da mesma maneira. Apenas vou usar uma variável j no lugar de i, pois já usei i para o laço mais externo. Note que o mesmo comando range serve para os dois laços.

Finalmente, não especificamos como deve ser o passo “troque elementos”. Vamos traduzi-lo.

A maneira clássica de fazer essa troca é usando uma variável temporária para guardar valor de um elemento e depois copiar os valores, assim:

temp = a

a = b

b = temp

Isso é necessário para guardar o valor da primeira variável antes de sobrescrevê-la, porém Python pode fazer isso de forma mais direta:

a, b = b, a

Python avalia as expressões da direita antes de fazer a atribuição às variáveis da esquerda, deste modo, pode-se fazer a troca do valor das variáveis sem que seja necessária uma variável temporária. Mas, lembre-se, isto é uma característica de Python; outras linguagens de programação não têm esse mecanismo e você deve usar a variável auxiliar.

Para definir a lista de números a ser ordenada, basta

simplesmente escrever no programa principal:

lista_desordenada = [

503, 87, 512, 61, 908, 170, 897, 275, 653, 426,

154,

509, 612, 677, 765, 703

]

 

■ Programa 8.1: Uma lista com n elementos fora de ordem.

 

No Programa 8.1, usei os mesmos números de Donald Knuth, no

seu famoso livro sobre a arte da programação de computadores [Knuth98a].

Juntando todos estes trechos de acordo com o algoritmo original,

temos o Programa 8.2.

def bubblesort(lista):

“““Ordena uma lista”””

n = len(lista)

print(lista)

for i in range(n - 1):

for j in range(n - 1):

if lista[j] > lista[j + 1]:

lista[j],lista[j + 1] = lista[j + 1],lista[j

]

print(lista)

lista_desordenada = [

503, 87, 512, 61, 908, 170, 897, 275, 653, 426,

154,

509, 612, 677, 765, 703

]

bubblesort(lista_desordenada)

 

■ Programa 8.2: Programa de ordenação pelo método da

bolha.

No programa, a lista é impressa a cada vez que é percorrida. Isso foi intencional para que você possa acompanhar a evolução da ordenação enquanto os passos são executados. Note que o maior elemento, aquele “mais pesado”, vai lentamente sendo colocado no

final da lista, borbulhando, daí o nome do algoritmo. A Figura 8.2 ilustra a execução deste programa. Cada coluna representa uma execução completa do laço.

 

Figura 8.2 Ordenação pelo método da bolha.

 

O objetivo de ordenar uma lista foi alcançado, mas esta solução está longe de ser eficiente. Se você analisou a resposta, deve ter percebido que muitas melhorias poderiam ser feitas. Quais seriam? Perceba que a partir de determinado ponto, nenhum elemento muda mais de posição. Nossa lista já está ordenada, mas o programa continua executando. A causa para isso é que o programa executa o laço n-1 vezes, independentemente de a lista estar ou não ordenada. Imagine que nossa lista estivesse ordenada desde o início. Mesmo assim o programa executaria n-1 vezes. Obviamente, temos de melhorar isso.