8.1.1 Sentinela

Como você pode saber se uma lista está ordenada? No algoritmo do ordenamento por borbulhamento é feita a comparação de elementos consecutivos de uma lista. Se em uma passagem não houver nenhuma troca, é porque a lista está ordenada e nada mais há para fazer, e pode-se dar o trabalho por concluído.

Uma forma simples de detectar se a lista está ordenada é usar

uma variável que controla se houve ou não uma mudança em determinada condição. Desse modo, em nosso exemplo de ordenação de lista, começamos acreditando que a lista está fora de ordem. Sabemos que a lista estará ordenada e poderemos parar, quando for feita uma passagem completa por todos os seus elementos sem que haja nenhuma troca, ou seja, em nenhum momento, durante essa passagem, o comando “if lista[j] > lista[j+1]:” teve como resultado verdade.

No nosso exemplo, vamos usar uma sentinela chamada

fora_de_ordem. Inicialmente seu valor é verdadeiro ( True), indicando que a lista está fora de ordem. Enquanto seu valor for verdadeiro, vamos continuar a varrer a lista, procurando elementos consecutivos fora de ordem. Para tanto, usaremos um artifício: logo antes de entrar no laço que faz essa varredura; faremos a sentinela ser falsa; mas, se alguma troca de elementos for realizada, o laço volta a ser verdade, indicando que a lista ainda não está ordenada. Quando o programa terminar o laço, se nenhuma troca foi feita, a sentinela continua com valor falso e o laço principal não executa outra vez, terminando o algoritmo; porém, se tiver havido alguma troca, o laço principal executa mais uma varredura.

A versão do algoritmo com sentinela seria:

Seja uma lista com n elementos

fora_de_ordem = verdade

Enquanto fora_de_ordem:

fora_de_ordem = falso

Para i variando entre 0 e n-2:

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

troque elementos de posição.

fora_de_ordem = verdade

O comando

Enquanto fora_de_ordem:

poderia ser escrito como

Enquanto fora_de_ordem == verdade:

mas isso seria redundante: o comando “ Enquanto” executa um laço enquanto uma condição for verdadeira, portanto, testar esta condição explicitamente é desnecessário. Além do mais, “ Enquanto fora_de_ordem: ” fica bem mais elegante e próximo ao português do que a versão explícita. O programa 8.3 traduz este algoritmo para Python.

def bubblesort(lista):

“““Ordena uma lista pelo método da bolha”””

n = len(lista)

fora_de_ordem = True

while fora_de_ordem:

fora_de_ordem = False

for j in range(n - 1):

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

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

j]

fora_de_ordem = True

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.3: programa de ordenação pelo método da bolha

com sentinela.

Em relação à versão sem a sentinela, o novo programa

economizou uma execução do laço. Pode parecer pouco, mas imagine que nossa lista já estivesse ordenada desde o início. O primeiro programa executaria o mesmo número de vezes, dependente apenas do tamanho da lista, enquanto a nova versão executaria o laço apenas uma vez e, ao terminar a primeira execução do laço, detectaria que a lista já estava ordenada e terminaria o programa.

Isso nos leva a uma conclusão interessante: apesar de ser

considerado um dos piores algoritmos de ordenação, o algoritmo da bolha pode ser o mais eficiente no caso particular em que a lista a ser ordenada já está ordenada! Não é muito útil, mas é um fato. Esse algoritmo detecta mais rapidamente que outros algoritmos essa condição, porém será extremamente ineficiente se o menor elemento estiver na última posição da lista. Neste caso, a cada passagem, este elemento “desce” apenas uma posição, e o programa vai precisar executar n-1 vezes para terminar de ordenar todos os elementos, e no caso de se usar sentinela, ainda executará uma última vez para confirmar se a lista está ordenada.

EXERCÍCIO 8.1

Python pode comparar strings diretamente com os operadores de comparação

usuais. Use o algoritmo da ordenação por borbulhamento para ordenar uma lista

de nomes. Para tanto, basta substituir a lista de números original por uma com

nomes, por exemplo:

lista = [‘Cleese’, ‘Palin’, ‘Jones’, ‘Idle’, ‘Gillia

m’, ‘Chapman’]

(como curiosidade, estes são os nomes dos atores do grupo Monty Python,

inspiração para o nome da linguagem Python)

Coloque mais palavras, e veja a diferença entre letras maiúsculas e

minúsculas. Qual palavra vem antes, ‘Cleese’, com c maiúsculo, e ‘cleese’.