8.2 Ordenação por Inserção

EXERCÍCIO 8.2

 

Uma melhoria pode ser feita no algoritmo da bolha com sentinela: note que a

cada passagem pela lista, a última troca de elementos deixa um elemento na sua

posição correta. Após esta posição, os elementos têm de estar ordenados e nos

próximos passos não é necessário ir além desta posição. Escreva um programa que

guarde esta posição e que a utilize como sentinela. O algoritmo a ser

implementado em Python é o seguinte:

Seja uma lista com n elementos

limite = tamanho da lista - 1

ultimo = limite

Enquanto limite != 0:

limite = 0

Para i variando entre 0 e ultimo - 1:

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

troque elementos de posição.

limite = i

ultimo = limite

Este algoritmo usa a variável limite para indicar qual elemento não

sabemos ainda estar na sua posição nal. Inicialmente a variável indica que não

sabemos nada sobre a lista. A variável ultimo indica o índice no qual foi

realizada a última troca entre posições de elementos. É fácil perceber que

limite funciona como uma sentinela. Se nenhuma troca for realizada,

limite permanece em zero e o algoritmo termina. A diferença aqui é que o

laço interno pode ser executado menos vezes, agilizando a ordenação.

 

8.2 ORDENAÇÃO POR INSERÇÃO

Existem outros algoritmos de ordenação mais eficientes que o algoritmo da bolha. Um dos mais simples é o de ordenação por inserção.

Figura 8.3 Ordenamento por inserção. Fonte: gvictoria |

iStockphoto.com.

 

Imagine que você quer ordenar um baralho de cartas. Você pega

as duas primeiras cartas e as coloca em ordem. Agora você vai pegar a terceira carta. As duas primeiras já estão ordenadas, então você só tem que encontrar a posição correta desta nova carta dentro do conjunto ordenado de cartas em sua mão. Para isso, começando pela última carta ordenada, você compara sucessivamente cada nova carta com a carta que tem nas mãos até achar uma que seja menor. Neste ponto você insere a carta em seu lugar correto. Esse processo, de pegar a próxima carta e compará-la com as cartas de sua mão, repete-se até que a posição correta de cada uma das cartas seja encontrada.

Passando isso para nosso exemplo numérico, temos a Figura

8.4.

Começando a desenvolver o algoritmo:

Para ordenar uma lista de n elementos em ordem crescente,

comparamos o segundo elemento com o primeiro, e, se estiverem fora de ordem, trocamos de posição. Depois inserimos o terceiro elemento dentro do conjunto ordenado até o segundo elemento. Passamos para o quarto elemento e o inserimos no conjunto já ordenado. Fazemos isso com cada elemento até chegarmos ao último, quando todos estarão ordenados.

 

Figura 8.4 Três passos do algoritmo de ordenamento por inserção.

 

O restante do desenvolvimento ficará como exercício.

O programa seguinte é o produto final deste algoritmo. Imprime a lista a cada passo para facilitar o acompanhamento da ordenação.

 

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

Inserção.

 

def insert_sort(lista):

"""Ordena uma lista pelo método da inserção"""

for j in range(1, len(lista)):

i = j - 1

elemento = lista[j]

while i >= 0 and lista[i] > elemento:

lista[i + 1] = lista[i]

i -= 1

lista[i + 1] = elemento

print(lista)

l = [

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

154,

509, 612, 677, 765, 703

]

insert_sort(l)

Perceba que, no caso desta ordenação, é o elemento mais “leve” que vai vagarosamente para seu lugar.

EXERCÍCIO 8.3

 

A partir da de nição do algoritmo de ordenação, siga os mesmos passos de

desenvolvimento do algoritmo da bolha para chegar à sua própria versão do

algoritmo de ordenação por inserção.

 

EXERCÍCIO 8.4

 

Um algoritmo recursivo para o ordenamento por inserção seria:

1 - Se lista tem tamanho igual ou menor que 1 retorn

e

2 - Recursivamente ordene os primeiros n-1 elementos

3 - Insira o último elemento na parte já ordenada

 

Você poderia escrever a função desse algoritmo? Perceba que a inserção ainda

deve ser feita com um laço. Este algoritmo não ganha em ser implementado

recursivamente. O desempenho das duas versões é equivalente.

 

EXERCÍCIO 8.5

 

Escreva uma função que intercale duas listas. O programa deve receber duas listas

já ordenadas e criar uma terceira lista que é o resultado da intercalação dos

elementos dos dois conjuntos de modo que a nova lista também esteja ordenada.

 

EXERCÍCIO 8.6

 

Um algoritmo bem e ciente de ordenação é o mergesort. Seu princípio é a

divisão do conjunto a ser ordenado em duas partes, ordenar cada parte, e depois

fazer uma fusão (merge, em inglês) entre os dois conjuntos ordenados. Cada vez

que for ordenar uma metade, o algoritmo é chamado recursivamente, dividindo à

metade cada parte que deveria ordenar. Quando a parte a ser ordenada contiver

apenas 1 elemento, o algoritmo retorna. O algoritmo usa também uma função