Buscar

Apostila - ALGORITMOS E ESTRUTURA DE DADOS II

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

�PAGE �
�PAGE �22�
ALGORITMOS E ESTRUTURA DE DADOS II
Leandro Rosniak Tibola
E-mail: tibola@fw.uri.br
Página Pessoal: www.fw.uri.br/~tibola
Sumário
	1 Listas Lineares
	3
	1.1 Alocação Estática versus Dinâmica
	4
	1.2 Alocação Seqüencial
	4
	1.3 Alocação Encadeada
	5
	
	
	2 Pilhas
	6
	2.1 Declarando e inicializando uma pilha
	7
	2.2 Verificando limites da pilha
	7
	2.3 Inserindo e removendo elementos na pilha
	7
	2.4 Verificando o elemento do topo da pilha
	8
	
	
	3 Filas
	9
	3.1 Declarando e inicializando uma fila
	10
	3.2 Verificando limites da fila
	10
	3.3 Inserindo e removendo elementos da fila
	10
	3.4 Problemas na implementação seqüencial de filas
	11
	3.5 Implementação circular para filas
	11
	3.6 Inserindo e removendo elementos da fila circular
	12
	
	
	4 Classificação por Inserção
	13
	4.1 Método da Inserção Direta.
	13
	4.1.1 Exemplo e implementação de Inserção Direta
	13
	4.1.2 Análise do Desempenho
	14
	4.2 Inserção Direta com Busca Binária
	15
	4.3 Método dos Incrementos Decrescentes - Shellsort
	16
	4.3.1 Exemplo Incrementos Decrescentes – Shellsort
	16
	4.3.2 Implementação
	17
	4.3.3 Análise do Desempenho
	17
	
	
	5 Classificação por Trocas
	19
	5.1 Método da Bolha – Bubblesort
	19
	5.1.1 Implementação
	20
	5.1.2 Análise do Desempenho
	20
	5.2 Método da Agitação - Shakesort
	21
	5.3 Método do Pente – Combsort
	21
	5.4 Método de Partição e Troca - Quicksort
	22
	5.4.1 Descrição do Método
	23
	5.4.2 Implementação
	25
	5.4.3 Análise do Desempenho
	26
	
	
	6 Classificação por Seleção
	29
	6.1 Método de Seleção Direta
	29
	6.1.1 Implementação
	29
	6.1.2 Análise do Desempenho
	30
	6.2 Método da Seleção em Árvore – HeapSort
	30
	6.2.1 Exemplo
	32
	6.2.2 Implementação
	37
	6.2.3 Análise do Desempenho
	38
	6.3 Método de Seleção em Árvore Amarrada – ThreadedHeapSort
	38
	
	
	7 Classificação por Distribuição de Chaves - Radixsort
	41
	7.1 Implementação
	43
	7.2 Desempenho
	45
	
	
	8 Classificação por Intercalação
	46
	8.1 Implementação
	46
	8.2 Análise do Desempenho
	49
	
	
	9 Listas Ordenadas
	51
	9.1 Implementação Encadeada para Listas Ordenadas
	51
	9.1.1 A Operação de Inserção
	52
	9.1.2 A operação de Remoção
	54
	9.1.3 A Operação de Pesquisa
	55
	9.1.4 Imprimindo uma Lista Ordenada
	56
	9.1.5 Destruindo uma Lista Ordenada
	57
	9.2 Técnicas de Encadeamento – Nodos cabeça e sentinela
	57
	9.3 Encadeamento circular
	59
	9.4 Encadeamento Duplo
	61
	
	
	Bibliografia
	62
	
	
	Lista de exercícios
	63
�
1	LISTAS LINEARES
Uma das formas mais comumente usadas para se manter dados agrupados é a lista. Afinal, quem nunca organizou uma lista de compras antes de ir ao mercado, ou então uma lista dos amigos que participarão da festa? As listas têm-se mostrado um recurso bastante útil e eficiente no dia-a-dia das pessoas. Em computação, não tem sido diferente: a lista é uma das estruturas de dados mais empregadas no desenvolvimento de programas.
Uma lista linear é uma coleção L: [a1, a2, ... an ], n .>= 0, cuja propriedade estrutural baseia-se apenas na posição relativa dos elementos, que são dispostos linearmente. Se n = 0 dizemos que a lista é vazia; caso contrário, são válidas as seguintes propriedades:
a1 é o primeiro elemento de L;
an é o último elemento de L;
ak , 1 < k < n, é precedido pelo elemento ak - 1 e seguido pelo elemento ak + 1 em L.
Em outras palavras, a característica fundamental de uma lista linear é o sentido de ordem unidimensional dos elementos que a compõem. Uma ordem que nos permite dizer com precisão onde a coleção inicia-se e onde termina, sem possibilidade de dúvida. Entre as diversas operações que podemos realizar sobre listas, temos:
acessar um elemento qualquer da lista;
inserir um elemento numa posição específica da lista;
remover um elemento de uma posição específica da lista;
combinar duas listas em uma única;
particionar uma lista em duas;
obter cópias de uma lista;
determinar o total de elementos na lista;
ordenar os elementos na lista
procurar um determinado elemento na lista;
apagar uma lista;
outras ...
Considerando-se somente as operações de acesso, inserção e remoção, restritas aos extremos da lista, temos casos especiais que aparecem muito freqüentemente na modelagem de problemas a serem resolvidos por computador. Tais casos especiais recebem também nomes especiais:
Pilha: lista linear onde todas as inserções, remoções e acessos são realizados em um único extremo. Listas com esta característica são também denominadas lista LIFO (Last-In/Firs-Out) ou em português: UEPS (Último que Entra/Primeiro que Sai).
Fila: lista linear onde todas as inserções são feitas num certo extremo e todas as remoções e acessos são realizados no outro extremo. Filas são também denominadas listas FIFO (First-In/First-Out) ou em português: PEPS (Primeiro que Entra/Primeiro que Sai).
Fila Dupla: lista linear onde as inserções, remoções ou acessos são realizados em qualquer extremo. Filas Duplas são também denominadas DEQUE (Double-Ended QUEue), ou em português: fila de extremidade dupla. Uma Fila Dupla pode ainda gerar dois casos especiais:
Fila Dupla de Entrada Restrita (se a entrada for restrita a um único extremo) e
Fila Dupla de Saída Restrita (se a remoção for restrita a um único extremo).
Ao desenvolver uma implementação para listas lineares, o primeiro problema que surge é: como podemos armazenar os elementos da lista, dentro do computador? Sabemos que antes de executar um programa, o computador precisa carregar seu código executável para a memória. Da área de memória que é reservada para o programa, uma parte é usada para armazenar as instruções a serem executadas e a outra é destinada ao armazenamento dos dados. Quem determina quanto de memória será usado para as instruções é o compilador. Alocar área para armazenamento de dados entretanto, é responsabilidade do programador. A alocação de memória, do ponto de vista do programador, estará em uma das quatro categorias apresentadas a seguir:
	
	Seqüencial
	Encadeada
	Estática
	Estática Seqüencial
	Estática Encadeada
	Dinâmica
	Dinâmica Seqüencial
	Dinâmica Encadeada
1.1	Alocação Estática versus Dinâmica
Dizemos que as variáveis de um programa têm alocação estática se a quantidade de memória utilizada pelos dados é previamente conhecida e definida de modo imutável, no código-fonte do programa; durante a execução, a quantidade de memória utilizada não varia. Por outro lado, se o programa é capaz de criar novas variáveis enquanto executa, isto é, se as áreas de memória, que não foram declaradas no programa, passam a existir durante a sua execução, então dizemos que a alocação é dinâmica.
Considerando que uma variável é que uma área de memória, dizemos que sua alocação é estática se sua existência já era prevista no código do programa; de outra forma, dizemos que sua alocação é dinâmica. A seguir, vemos o uso de variável estática em contraste com variável dinâmica:
program alocacao;
type ptr = ^integer;
var P: ptr; {aloca variável estaticamente}
begin
new(P); {aloca variável dinamicamente}
P^ := 12345;
writeln(P^);
end.
Observando a figura, com a memória no momento da execução, verificamos que mais uma variável foi criada na posição de memória 1FFA. Esta é uma variável alocada dinamicamente (às vezes denominada variável anônima, pois não conhecemos seu nome, temos apenas seu endereço!).
Os atributos seqüencial e encadeada só têm sentido se formos armazenar uma coleção de objetos, como é o caso da memória necessária para armazenar uma lista linear ou um vetor.
1.2	Alocação Seqüencial
A forma mais natural de armazenar uma lista consiste em colocar os seus elementos em células
de memória consecutivas. Assim, se cada célula tem um endereço único E e utiliza k bytes, temos:
Endereço(ai ) = E ;
Endereço(ai -1) = E-k ;
Endereço(ai +1) = E+k .
De forma um pouco mais genérica, assumindo que o elemento a1 encontra-se na célula de endereço B, temos a equação: Endereço(ai ) = B + (i-1)k.
A maior vantagem no uso de uma área seqüencial de memória para armazenar uma lista linear é que, dado o endereço inicial B da área alocada e o índice i de um elemento qualquer da lista, podemos acessá-lo imediatamente, com um simples e rápido cálculo. O ponto fraco desta forma de armazenamento aparece quando precisamos inserir ou suprimir elementos do meio da lista, quando então um certo esforço será necessário para movimentar os elementos, de modo a abrir espaço para inserção, ou de modo a ocupar o espaço liberado por um elemento que foi removido.
1.3	Alocação Encadeada
Ao invés de manter os elementos agrupados numa área contínua de memória, isto é, ocupando células consecutivas, na alocação encadeada os elementos podem ocupar quaisquer células (não necessariamente consecutivas) e, para manter a relação de ordem linear, juntamente com cada elemento é armazenado o endereço do próximo elemento da lista. Desta forma, na alocação encadeada, os elementos são armazenados em blocos de memória denominados nodos, sendo que cada nodo é composto por dois campos: um para armazenar dados e outro para armazenar endereço. Dois endereços especiais devem ser destacados (como visto na figura):
endereço do primeiro elemento da lista (L);
endereço do elemento fictício que segue o último elemento da lista (nil).
A alocação encadeada apresenta como maior vantagem a facilidade de inserir ou remover elementos do meio da lista. Como os elementos não precisam estar armazenados em posições consecutivas de memória, nenhum dado precisa ser movimentado, bastando atualizar o campo de ligação do elemento que precede aquele inserido ou removido. Por exemplo, para remover o elemento a2 da lista representada na figura, basta mudar o nodo no endereço 3FFA de (a1,1C34) para (a1,BD2F). Como apenas o primeiro elemento é acessível diretamente através do endereço L, a grande desvantagem da alocação encadeada surge quando desejamos acessar uma posição específica dentro da lista. Neste caso, devemos partir do primeiro elemento e ir seguindo os campos de ligação, um a um, até atingir a posição desejada. Obviamente, para listas extensas, esta operação pode ter um alto custo em relação a tempo.
�
2	PILHAS
A pilha é uma das estrutura de dados mais úteis em computação. Uma infinidade de problemas clássicos da área podem ser resolvidos com o uso delas. Uma pilha é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas numa mesma extremidade, denominada topo. Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no seu topo; e em qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido.
Devido a esta disciplina de acesso, os elementos são sempre removidos numa ordem inversa àquela em que foram inseridos, de modo que o último elemento que entra é exatamente o primeiro que sai. Daí o fato destas listas serem também denominadas listas LIFO (Last-In/First-Out) ou em português: UEPS (Último que Entra/Primeiro que Sai).
Uma pilha ou lista LIFO é uma coleção que pode aumentar ou diminuir durante a sua existência. O nome pilha advém justamente da semelhança entre o modo como as listas LIFO crescem e diminuem e o modo como as pilhas, no mundo real, funcionam. O exemplo mais comum do quotidiano é uma pilha de pratos, onde o último prato colocado é o primeiro a ser usado (removido da pilha).
Uma pilha suporta 3 operações básicas, tradicionalmente denominadas como:
Top (Visualizar o Topo): acessa o elemento posicionado no topo da pilha;
Push (Inserir): insere um novo elemento no topo da pilha;
Pop (Retirar): remove um elemento do topo da pilha.
Sendo P uma pilha e x um elemento qualquer, a operação Push ( P, x ) aumenta o tamanho da pilha P, acrescentando o elemento x no seu topo. A operação Pop ( P ) faz com que a pilha diminua, removendo e retornando o elemento existente em seu topo. A operação Top não altera o estado da pilha; apenas retorna uma cópia do elemento existente no topo da pilha sem removê-lo.
Exercício: Dadas as operações sobre uma pilha P, preencha o quadro a seguir com o estado da pilha e o resultado de cada operação:
Como os elementos da pilha são armazenados em seqüência, um sobre o outro, e a inclusão ou exclusão de elementos não requer movimentação de dados, o esquema de alocação seqüencial de memória mostra-se bastante apropriado para implementá-las. Neste esquema, a forma mais simples de se represntar uma pilha na memória consiste em :
um vetor, que serve para armazenar os elementos contidos na pilha;
um índice, utilizado para indicar a posição corrente de topo da pilha.
Note-se que vetor é o mecanismo oferecido pelas linguagens de programação que nos premite alocar, de forma estática, uma área seqüencial de memória; o índice é o recurso necessário para disciplinar o acesso aos elementos da pilha.
2.1 Declarando e inicializando uma pilha
Para declarar uma pilha, precisamos então de duas variáveis: um vetor com o tamanho necessário para armazenar as informações e uma variável que indica o topo. Para inicializar uma pilha, deve-se inicializar o topo:
Program Pilha;
const MAX = 10;
var
V: array[1..MAX] of integer;
topo: integer;
begin
topo := 0;
2.2 Verificando limites da pilha
Uma inserção só pode ser feita na pilha se o topo for menor que o seu tamanho máximo, caso contrário ocorre o que se chama de estouro de pilha ou stack overflow. Da mesma forma, uma retirada só pode ser feita se o topo for maior que zero, caso contrário ocorre o que se chama de stack underflow.
Para verificar se uma pilha está cheia, basta testar se o topo é igual ao seu tamanho máximo. O teste para verificar se pode ser feita uma inserção numa pilha que tem tamanho máximo igual a 10 é mostrado no exemplo abaixo. Para verificar se uma pilha está vazia, basta testar se o topo é inferior a zero. O teste para verificar se pode ser feita uma retirada é mostrado no exemplo abaixo:
if topo = MAX
then writeln(‘Pilha cheia!’);
if topo = 0
then writeln(‘Pilha vazia!’);
2.3 Inserindo e removendo elementos da pilha
Para inserir um elemento na pilha, precisamos saber qual é o elemento a ser inserido e testar se a pilha está cheia. Se não estiver cheia, incrementamos o topo e, nesta posição, inserimos o novo elemento. 
Para remover um elemento na pilha, precisamos saber se a pilha não está vazia. Se a mesma não está vazia, mostra-se o valor que está no vetor na posição apontada pelo topo e decrementa-se o topo. O exemplo abaixo ilustra a inserção e remoção de um elemento da pilha:
Program Pilha;
Uses Crt;
const MAX = 10;
Var
V: Array[1..MAX] of integer;
topo: integer;
x: integer;
Begin
topo := 0; // inicialização da pilha
{ --- procedimento para inserção --- }
write(‘Valor a inserir: ‘);
readln (x);
if topo = MAX
then writeln(‘Pilha cheia!’);
else begin
topo := topo + 1;
V[topo] := x;
end;
{ --- procedimento para retirada --- }
if topo = 0
then writeln(‘Pilha vazia!’);
else begin
writeln(‘O valor retirado é: ‘, V[topo]);
topo := topo - 1;
end;
end.
2.4 Verificando o elemento do topo da pilha
Para verificar o elemento que está no topo da pilha, verificamos se a pilha está vazia. Se não estiver vazia, mostra-se o valor que está no vetor na posição apontada pelo topo sem decrementar o topo. 
if topo = 0
then writeln(‘Pilha vazia!’);
else writeln(‘O valor que está no topo é: ‘, V[topo]);
�
3	FILAS
Uma fila é um tipo especial de lista linear em que as inserções são realizadas em um extremo e as remoções são feitas no outro. Cada vez
que uma operação de inserção é executada, um novo elemento é colocado no final da fila. Na remoção, é retornado o elemento que aguarda há mais tempo na fila, posicionado no começo. A ordem de saída corresponde à ordem de entrada dos elementos na fila, de modo que os primeiros elementos que entram são sempre os primeiros a sair. Por este motivo, as filas são denominadas listas FIFO (First-In/First-Out) ou PEPS (Primeiro que Entra/Primeiro que Sai).
Um exemplo bastante comum de filas verifica-se num balcão de atendimento, onde pessoas formam uma fila para aguardar até serem atendidas. Naturalmente, devemos desconsiderar os casos de pessoas que .furam. a fila ou que desistem de aguardar! Diferentemente das filas no mundo real, o tipo abstrato de dados não suporta inserção nem remoção no meio da lista.
A palavra inglesa queue significa fila. As operações básicas que uma fila suporta são:
Enqueue (Inserir): insere um novo elemento no final da fila;
Dequeue (Retirar): remove um elemento do começo da fila.
Sendo F uma fila e x um elemento qualquer, a operação Enqueue ( F, x ) aumenta o tamanho da fila F , acrescentando o elemento x no seu final. A operação Dequeue ( F ) faz com que a fila diminua, removendo e retornando o elemento existente em seu começo.
Exercício: Dadas as operações sobre uma fila F, preencha o quadro a seguir com o estado da fila e o resultado de cada operação:
Graficamente, representamos uma fila como uma coleção de objetos que cresce da esquerda para a direita, com dois extremos bem definidos: começo e final:
3.1 Declarando e inicializando uma fila
A partir da representação gráfica podemos implementar uma fila tendo três recursos básicos:
espaço de memória para armazenas os elementos (um vetor V);
uma referência ao primeiro elemento da coleção (uma variável começo);
uma referência à primeira posição livre, após o último elemento da fila (uma variável final).
Para inicializar a fila, deve-se atribuir o valor 1 às variáveis começo e final da fila:
Program Fila;
const MAX = 10;
Var
V: Array[1..10] of integer;
comeco, final : integer;
Begin
comeco := 1;
final := 1;
3.2 Verificando limites da fila
Uma inserção só pode ser feita se a fila não estiver cheia (final menor que o seu tamanho máximo). Da mesma forma, uma retirada só pode ser feita se existirem elementos na fila (o começo for diferente do final). Para verificar se a fila está cheia, basta testar se o final é maior que o seu tamanho máximo; para verificar se a fila está vazia, basta testar se o começo é igual ao final. Os testes para verificar se pode ser feita uma inserção numa fila que tem tamanho máximo igual a 10, bem como se pode ser feita uma retirada, são mostrados no exemplo abaixo.
if final > MAX
then writeln(‘Fila cheia!’);
if comeco = final
then writeln(‘Fila vazia!’);
3.3 Inserindo e removendo elementos na fila
Para inserir um elemento na fila, precisamos saber qual é o elemento a ser inserido e testar se a fila está cheia. Se não estiver cheia, o elemento é inserido na posição apontada pela variável final, que deve ser incrementada depois da inserção. Para remover um elemento da fila, precisamos saber se a fila não está vazia. Se não estiver vazia, mostra-se o valor que está no vetor na posição apontada pelo começo e incrementa-se o começo. O exemplo abaixo ilustra a inserção e remoção de um elemento.
{ --- procedimento para inserção --- }
write(‘Valor a inserir: ‘);
readln (x);
if final > MAX
then writeln(‘Fila cheia!’);
else begin
V[final] := x;
final := final + 1
end;
{ --- procedimento para retirada --- }
if comeco = final
then writeln(‘Fila vazia!’);
else begin
writeln(‘O valor retirado é: ‘, V[comeco]);
comeco := comeco + 1;
end;
3.4 Problemas na implementação seqüencial de filas
Vimos que cada vez que um elemento é removido, o índice que aponta o começo da fila desloca-se uma posição à direita (incrementado). Supondo que a fila tenha um tamanho máximo de 10, após 10 inserções o ponteiro que aponta para o final da fila tem o valor 11 e a fila estará cheia, pois o final maior que o tamanho máximo representa fila cheia, não podendo ser inserido mais nenhum elemento. Após 10 retiradas, o ponteiro que aponta para o começo da fila terá o valor 11 e a fila estará vazia, pois o começo igual ao final representa fila vazia. Chegamos a uma situação extremamente indesejável: temos uma fila cheia e vazia ao mesmo tempo. Chegamos à conclusão de que esta nossa solução não é muito eficiente, apresentando tanto desperdício de memória quanto problemas de lógica.
Eliminar o erro lógico, que sinaliza fila vazia e cheia ao mesmo tempo, é bastante simples. Basta acrescentar uma variável para contar quantos elementos estão na fila; quando um elemento for inserido, ela será incrementada; quando for removido, será decrementada. Desta forma, o impasse pode ser resolvido simplesmente consultando essa variável.
Para eliminar o desperdício de memória, o ideal seria que cada posição liberada por um elemento removido se tornasse disponível para receber um novo elemento inserido. Para isso teríamos de dispor de uma área seqüencial de memória tal que a posição 1 estivesse imediatamente após a última posição. Assim, a fila somente estaria cheia, quando realmente tivesse um elemento para cada posição.
3.5 Implementação circular para filas
A partir da representação gráfica percebemos que é possível implementar uma fila circular tendo: 
espaço de memória para armazenas os elementos (um vetor V);
uma referência ao primeiro elemento da coleção (uma variável começo);
uma referência à primeira posição livre, após o último elemento da fila (uma variável final);
um indicador da quantidade de elementos da fila (uma variável qtd).
O exemplo abaixo declara uma fila de tamanho igual a 10 e inicializa seus valores:
Program FilaCircular;
const MAX = 10;
Var
V: Array[1..MAX] of integer;
qtd, comeco, final : integer;
Begin
comeco := 1;
final := 1;
qtd := 0;
Para verificar se a fila está cheia, basta testar se a variável contadora é igual ao seu tamanho máximo. Para verificar se a fila está vazia, basta testar se o começo é igual ao final. Estes testes são mostrados no exemplo abaixo.
if qtd = MAX
then writeln(‘Fila cheia!’);
if qtd = 0
then writeln(‘Fila vazia!’);
3.6 Inserindo e removendo elementos da fila circular
Para inserir um elemento na fila, precisamos saber qual é o elemento a ser inserido e testar se a fila está cheia; se não estiver cheia, o elemento é inserido na posição apontada pela variável final, que deve ser incrementada depois da inserção. Para remover um elemento da fila, precisamos saber se a fila não está vazia; se não estiver vazia, mostra-se o valor que está no vetor na posição apontada pelo comeco e incrementa-se o começo. O exemplo abaixo ilustra a inserção e remoção de um elemento da fila.
Program FilaCircular;
const MAX = 10;
Var
V: Array[1..MAX] of integer;
qtd, comeco, final, x : integer;
Begin
comeco := 1;
final := 1;
qtd := 0; // inicialização da fila
{ --- procedimento para inserção --- }
write(?Valor a inserir: ?);
readln (x);
if qtd = MAX
then writeln(‘Fila cheia!’);
else begin
V[final] := x;
qtd := qtd + 1;
if final = MAX
then final := 1;
else final := final + 1;
end;
{ --- procedimento para retirada --- }
if qtd = 0
then writeln(‘Fila vazia!’);
else begin
writeln(‘O valor retirado é: ‘, V[comeco]);
qtd := qtd - 1;
if comeco = MAX
then comeco := 1 ;
else comeco := comeco + 1;
end;
end.
�
4	CLASSIFICAÇÃO POR INSERÇÃO
Na classificação por inserção, os n dados a serem ordenados são divididos em dois segmentos: um já ordenado e outro a ser ordenado. Num momento inicial, o primeiro segmento é formado por apenas um elemento, portanto, já ordenado; o segundo segmento é formado
pelos restantes n-1 elementos. A partir daí, o processo se desenvolve em n-1 iterações: em cada uma delas um elemento do segmento não ordenado é transferido para o primeiro segmento, inserido em sua posição correta em relação àqueles que para lá já foram transferidos. Os métodos que pertencem a esta família diferem um dos outros apenas pela forma como localizam a posição em que cada elemento deve ser inserido no segmento já ordenado.
4.1 Método da Inserção Direta
Neste método, considera-se o segmento já ordenado como sendo formado pelo primeiro elemento do vetor de chaves. Os demais elementos, ou seja do 2º ao último, pertencem ao segmento não ordenado. A partir desta situação inicial, toma-se um a um dos elementos não ordenados, a partir do primeiro e, por busca seqüencial realizada da direita para a esquerda no segmento já ordenado, localiza-se a sua posição relativa correta. A cada comparação realizada entre o elemento a ser inserido e os que lá já se encontram, podemos obter um dos seguintes resultados:
O elemento a ser inserido é menor do que aquele com que se está comparando. Nesse caso, este é movido uma posição para a direita, deixando, assim, vaga a posição que anteriormente ocupava.
O elemento a ser inserido é maior ou igual àquele com que se está comparando. Nesse caso, fazemos a inserção do elemento na posição vaga, a qual corresponde à sua posição relativa correta no segmento já ordenado. Caso o elemento a ser inserido seja maior do que todos, a inserção corresponde a deixá-lo na posição que já ocupava.
Após a inserção, a fronteira entre os dois segmentos é deslocada uma posição para a direita: o segmento ordenado ganha um elemento e o não ordenado perde um. O processo prossegue até que todos os elementos do segundo segmento tenham sido inseridos no primeiro.
4.1.1 Exemplo e implementação de Inserção Direta
	vetor original 
	18
	15
	7
	9
	23
	16
	14
	
	divisão inicial
	18
	15
	7
	9
	23
	16
	14
	não ordenado
	
	
	ordenado
	
	
	
	
	primeira iteração
	15
	18
	7
	9
	23
	16
	14
	
	segunda iteração
	7
	15
	18
	9
	23
	16
	14
	
	terceira iteração
	7
	9
	15
	18
	23
	16
	14
	
	quarta iteração
	7
	9
	15
	18
	23
	16
	14
	
	quinta iteração
	7
	9
	15
	16
	18
	23
	14
	
	sexta iteração
	7
	9
	14
	15
	16
	18
	23
	vetor ordenado
{ --- declaração do vetor, anterior --- }
const MAX = 10;
Var V: Array[1..MAX] of integer;
{ --- declaração da procedure de inserção --- }
procedure InsercaoDireta;
Var aux, i, j: integer;
Begin
for j := 2 to MAX
do begin
aux := V[j];
i := j - 1;
while ((i > 0) and (V[i] > aux))
do begin
V[i+1] := V[i];
i := i – 1;
end;
V[i+1] := aux;
end;
end;
A implementação acima demonstra a descrição formulada: o segmento já ordenado é percorrido da direita para a esquerda, até que seja encontrada uma chave menor ou igual àquela que está sendo inserida, ou até que o segmento termine . Enquanto nenhuma dessas condições ocorrer, as chaves comparadas vão sendo deslocadas uma posição para a direita. Na hipótese da chave a ser inserida ser maior do que todas as do segmento ordenado, ela permanece no seu local original, caso contrário, é inserida na posição deixada vaga pelos deslocamentos, avançando-se, a seguir, a fronteira entre os dois segmentos . O processo todo é completado em n-1 iterações.
4.1.2 Análise do Desempenho
O desempenho do método da inserção direta é fortemente influenciado pela ordem inicial das chaves a serem ordenadas. Isto se deve principalmente ao fato de que as chaves que já estão no vetor ordenado, e que são maiores do que a que está sendo inserida, devem ser transpostas uma posição para a direita, para dar lugar àquela que vai ser inserida. Observe que, mesmo se usássemos um método de busca mais eficiente do que a linear, não evitaríamos a operação de transposição.
A situação mais desfavorável para o método é aquela em que o vetor a ser ordenado se apresenta na ordem contrária à desejada. Isto significa que cada elemento a ser inserido sempre será menor do que todos os que já estão no segmento ordenado. Isto acarreta um deslocamento de todos eles uma posição para a direita. A tabela a seguir mostra a quantidade de comparações e transposições necessárias para inserir cada uma das chaves:
	1ª
	chave:
	1
	2ª
	chave:
	2
	3ª
	chave:
	3
	...
	chave:
	...
	(n-1)a
	chave:
	n-1
O total corresponderá à soma do número de operações efetuadas em cada iteração: 1+2+3+...+(n.1), igual à soma dos termos de uma progressão aritmética cujo primeiro termo é 1 e o último é (n -1):
S = ( 1 + (n+1) ) / 2 * (n - 1) = (n² - n) / 2.
Por outro lado, o melhor caso para o método é aquele no qual as chaves já se apresentam previamente ordenadas. Nesta situação, cada chave a ser inserida sempre será maior do que aquelas que já o foram. Isto significa que nenhuma transposição é necessária. De qualquer maneira, é necessária pelo menos uma comparação para localizar a posição da chave. Logo, nesta situação, o método efetuará um total de n-1 iterações para dar o vetor como ordenado.
Podemos supor que em situações normais o vetor não se apresente já ordenado, nem tampouco com a ordenação inversa àquela desejada. É razoável imaginar uma situação intermediária entre os casos extremos, supondo que esta corresponda à média aritmética entre os dois casos. Assim, o desempenho médio do método é dado por:
( (n - 1) + ( (n² - n) / 2 ) ) / 2 = (n² + n - 2) / 4
Podemos também usar uma outra abordagem para estimar a complexidade do método. Examinaremos o seu desempenho para os casos de haver nenhuma, uma, duas, três, etc... chaves fora do seu local definitivo. Depois, generalizaremos para um certo valor médio de chaves fora do lugar.
Para cada caso, consideramos dois tipos de comparações: as necessárias para descobrir a posição correta das chaves que estão fora do seu lugar, e as necessárias para descobrir que as demais chaves já estão no seu local correto. Iremos supor que as chaves fora do local estão a uma distância média de n/2 posições, já que a distância mínima é 1 e a máxima é n-1.
A quantidade de chaves fora do local poderá variar de nenhuma até n-1, já que, mesmo que o vetor se apresente na ordem inversa àquela desejada, podemos considerar que pelo menos uma chave se encontra na sua posição correta, enquanto as n-1 demais se encontram deslocadas.
A tabela a seguir mostra a quantidade de comparações necessárias em cada caso. A coluna A indica a quantidade de chaves fora do seu local. A coluna B mostra o número de comparações efetuadas para descobrir o local correto de cada chave que está fora do seu lugar. Já a coluna C exibe o número de comparações para descobrir que as demais chaves estão no seu local correto.
	A
	B
	C
	0
	0
	n-1
	1
	n/2
	n-2
	2
	2 * n/2
	n-3
	3
	3 * n/2
	n-4
	...
	...
	...
	k = n - 1
	k * n/2
	n – (k-1)
O total de comparações para um certo 0 <= i <= k é, pois, a soma das comparações indicadas nas colunas B e C, ou seja: (i * n/2) + (n - (i+1)). De fato, para i = 0 e para i = k, temos, respectivamente, (n – 1) e ((n² - n) / 2) comparações, as quais correspondem ao melhor e ao pior caso do método, também respectivamente, na análise efetuada anteriormente. Considerando, como antes, que o caso médio corresponde à média aritmética entre o melhor e o pior caso, temos:
número médio de chaves fora do local = ( 0 + (n - 1)) / 2 = (n - 1) / 2
número médio de comparações = (n-1)/2 * (n/2) + (n- ((n-1)/2-1)) = (n² + n-2)/4 o que corresponde exatamente ao resultado encontrado na análise anterior.
4.2 Inserção Direta com Busca Binária
Como mencionamos no início desta seção, o uso de um método mais eficiente do que o da busca seqüencial pode ser usado para localizar a posição na qual uma certa chave deve ser inserida no segmento ordenado. Isto não nos livra, no entanto, da necessidade de efetuar os deslocamentos das
chaves que são maiores do que aquela que está sendo inserida, para lhe dar lugar.
Eventualmente poderíamos pensar em organizar o segmento ordenado sob a forma de uma lista encadeada, de tal forma a evitar a necessidade de deslocamentos. A inserção seria feita apenas com ajustes de ponteiros. Mas, por outro lado isto nos obrigaria a uma pesquisa seqüencial na lista para localizar o ponto de inserção. Isto nos deixa num impasse. Assim, mesmo melhorando o tempo de localização do ponto de inserção, ficamos ainda com o ônus dos elevados tempos de deslocamento.
Supondo, no entanto, que mesmo assim optemos por esta solução, vejamos então qual o seu comportamento. Sabemos que o número de comparações necessárias para localizar a posição que um elemento deve ocupar em uma tabela que contém k símbolos, por pesquisa binária, é aproximadamente log2 k. No nosso caso, esta operação será repetida para valores de k variando de 1 até n-1. Restam as operações de deslocamento que, como já sabemos, são realizadas em quantidades proporcionais ao quadrado do número de chaves. Sugerimos, como exercício, que demonstre que o número médio de deslocamentos necessários para inserir as n-1 chaves é (n² - n)/4.
Vemos, assim, que a alternativa de usar a pesquisa binária para rapidamente encontrar a posição de inserção não produz grandes ganhos no desempenho do método, pois após a localização, ainda é necessário promover os deslocamentos das chaves à direita da posição de inserção, que é uma operação de desempenho O(n²). Caso, no entanto, possamos dispor de uma arquitetura que execute deslocamentos em blocos, poderemos obter vantagens no tempo despendido com a operação.
Deixamos ainda a sugestão de implementar o método de classificação por inserção com busca binária, comparando-o com o de busca seqüencial.
4.3 Método dos Incrementos Decrescentes - Shellsort
Este método, proposto em 1959 por Donald L. Shell, explora o fato de que o método da inserção direta apresenta desempenho aceitável quando o número de chaves é pequeno ou já existe uma ordenação parcial. De fato, como o desempenho do método é quadrático, se dividirmos o vetor em h segmentos, de tal forma que cada um possua aproximadamente n/h chaves e classificarmos cada segmento separadamente, teremos, para cada um deles, um desempenho em torno de (n/h)2. Para classificar todos os h segmentos, o desempenho será proporcional a h * (n/h)2 = n2/h. Além disso, teremos rearranjado as chaves no vetor, de modo que elas se aproximem mais do arranjo final, isto é, teremos feito uma ordenação parcial do vetor, o que contribui para a diminuição da complexidade do método.
Para implementar o método, o vetor C[1..n] é dividido em segmentos, assim formados:
segmento 1: C[1], C[h+1], C[2h+1], ...
segmento 2: C[2], C[h+2], C[2h+2], ...
segmento 3: C[3], C[h+3], C[2h+3], ...
.....
segmento h: C[h], C[h+h], C[2h+h], ...
onde h é um incremento.
No exemplo consideraremos incrementos iguais a potências inteiras de 2. Num primeiro passo, para um certo h inicial, os segmentos assim formados são então classificados por inserção direta. Num segundo passo, o incremento h é diminuído (a metade do valor anterior, se este era uma potência inteira de 2), dando origem a novos segmentos, os quais também serão classificados por inserção direta. O processo se repete até que h=1. Quando for feita uma classificação com h=1, o vetor estará classificado. Observe que quando h=1, o método se confunde com o da inserção direta.
A vantagem reside no fato de que o método shell, em cada passo, faz classificações parciais do vetor, o que favorece o desempenho dos passos seguintes, uma vez que a inserção direta é acelerada quando o vetor já se encontra parcialmente ordenado (veja mais, em relação a desempenho, em Método de Inserção Direta).
4.3.1 Exemplo Incrementos Decrescentes - Shellsort
Convenção: os números acima de cada célula indicam os índices das chaves no vetor. Os números abaixo de cada célula indicam o número do segmento ao qual cada célula pertence.
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	17
	25
	49
	12
	18
	23
	45
	38
	53
	42
	27
	13
	11
	28
	10
	14
	1
	2
	3
	4
	1
	2
	3
	4
	1
	2
	3
	4
	1
	2
	3
	4
Primeiro passo: h = 4
Após classificar cada um dos quatro segmentos, o vetor terá o aspecto a seguir.
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	11
	23
	10
	12
	17
	25
	27
	13
	18
	28
	45
	14
	53
	42
	49
	38
	1
	2
	1
	2
	1
	2
	1
	2
	1
	2
	1
	2
	1
	2
	1
	2
Segundo passo: h = 2
Após classificar cada um dos dois segmentos, o vetor terá o aspecto seguinte:
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	10
	12
	11
	13
	17
	14
	18
	23
	27
	25
	45
	28
	49
	38
	53
	42
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
	1
Terceiro (e último) passo: h = 1
Após a execução do último passo, o vetor resultará classificado:
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	10
	11
	13
	13
	14
	17
	18
	23
	25
	27
	28
	38
	42
	45
	49
	53
4.3.2 Implementação
A implementação do método dos incrementos decrescentes é uma adaptação da implementação do método de inserção direta. Ao invés de classificar um vetor cujos elementos se encontram contíguos uns aos outros, classifica apenas os elementos do vetor que pertencem a um certo segmento: os elementos que iniciam numa dada célula f e estão espaçados entre si a uma distância h. 
{ --- declaração do vetor, anterior --- }
const MAX = 10;
Var V: Array[1..MAX] of integer;
{ --- declaração da procedure de inserção --- }
procedure shellSort;
const arrSaltos: array[1..5] of integer = (9,5,3,2,1);
Var salto, aux, i, j, k: integer;
Begin
for k := 1 to 5
do begin
salto := arrSaltos[k];
j := 1 + salto;
while j <= MAX
do begin
aux := V[j];
i := j – salto;
while ((i > 0) and (V[i] > aux))
do begin
V[i+salto] := V[i];
i := i – salto;
end;
V[i+salto] := aux;
j := j + salto;
end;
end;
end;
4.3.3 Análise do Desempenho
Segundo Knuth e Wirth, a análise do desempenho do método é muito complexa, pois enfrenta alguns problemas matemáticos bastante difíceis, alguns deles ainda não resolvidos. Um dos problemas é determinar o efeito que a ordenação dos segmentos em um passo produz nos passos subseqüentes. Também não se conhece exatamente a seqüência de incrementos que produz o melhor resultado. A este respeito, observa-se que os valores dos incrementos não podem ser múltiplos uns dos outros. Isto evita que se combine, em uma iteração, dois segmentos entre os quais não havia nenhuma iteração prévia. Esta iteração é desejável e deve ser a maior possível, de acordo com o teorema a seguir:
“Se a uma seqüência, previamente ordenada, de distância k, for em seguida aplicada uma ordenação de distância i, então essa seqüência permanece ordenada de distância k.” - D.Knuth
O autor do teorema mostra, por meio de simulações, que os melhores resultados obtidos foram com as seguintes seqüências de incrementos:
2k +1,...,9,5,3,1; k = ...3,2,1
2k - l,...,15,7,3,l; k = ...3,2,1
(2k - (-1) k) / 3,...,11,5,3,1; k = ...,3,2
(3k - 1) / 2, ...,40,13,4,1; k = ...,2,1
Observação: na primeira série o valor 1 foi inserido. Quanto ao valor inicial do incremento, é recomendado que seja aquele valor que divida o vetor de chaves no maior número possível de segmentos de mais de um elemento.
�
5	CLASSIFICAÇÃO POR TROCAS
Os métodos de classificação por trocas caracterizam-se por efetuarem a classificação por comparação entre pares de chaves, trocando-as de posição caso estejam fora de ordem no par.
5.1 Método da Bolha - Bubblesort
Neste método, o princípio geral é aplicado a todos os pares consecutivos de chaves. Este processo é executado enquanto houver pares consecutivos de chaves não ordenados. Quando não restarem
mais pares não ordenados, o vetor estará classificado.
Suponha que se deseje classificar em ordem crescente o seguinte vetor de chaves: 28 26 30 24 25. Comparamos todos os pares de chaves consecutivas, a partir do par mais à esquerda. Caso as chaves de um certo par se encontrem fora da ordem desejada, efetuamos a troca das mesmas. O processo de comparação dos n-1 pares de chaves é denominado de varredura. O método efetuará tantas varreduras no vetor quantas forem necessárias para que todos os pares consecutivos de chaves se apresentem na ordem desejada.
Primeira varredura:
28 26 30 24 25 compara par (28,26): troca.
26 28 30 24 25 compara par (28,30): não troca.
26 28 30 24 25 compara par (30,24): troca.
26 25 24 30 25 compara par (30,25): troca.
26 28 24 25 30 fim da primeira varredura.
Como ainda existem pares não ordenados, reiniciamos o processo de comparações de pares de chaves, executando mais uma varredura. Observe, no entanto, que a primeira varredura sempre irá posicionar a chave de maior valor na sua posição definitiva correta (no final do vetor). Isto significa que na segunda varredura podemos desconsiderar a última posição do vetor, que portanto fica reduzido de um elemento. Esta situação se repetirá ao final de cada varredura efetuada.
Segunda varredura:
26 28 24 25 30 compara par (26,28): não troca.
26 28 24 25 30 compara par (28,24): troca.
26 24 28 25 30 compara par (28,25): troca.
26 24 25 28 30 fim da segunda varredura.
Terceira varredura:
26 24 25 28 30 compara par (26,24): troca.
24 26 25 28 30 compara par (26,25): troca.
24 25 26 28 30 fim da terceira varredura.
Como não restam mais pares não ordenados, o processo de classificação é dado por concluído.
Examinando-se o comportamento do método, vemos que, dependendo da disposição das chaves, uma certa varredura pode colocar mais do que uma chave na sua posição definitiva. Isto ocorrerá sempre que houver blocos de chaves já previamente ordenadas, como no exemplo abaixo.
Vetor de chaves: 13 11 25 10 18 21 23
A primeira varredura produzirá o seguinte resultado: 11 13 10 18 21 23 25
Observe que, neste caso, as quatro últimas chaves já se encontram na sua posição definitiva. Isto significa que a próxima varredura não precisa ignorar apenas a última chave. As quatro últimas podem ser ignoradas. A quantidade de chaves, a partir da última, que pode ser ignorada de uma varredura para outra é conhecida pela posição na qual ocorreu a última troca. A partir daquele ponto o vetor já se encontra ordenado.
A denominação deste método resulta da associação das chaves com bolhas dentro de um fluido. Cada bolha teria um diâmetro proporcional ao valor de uma chave. Assim, as bolhas maiores subiriam mai depressa, o que faria com que, após um certo tempo, elas se arranjassem em ordem de tamanho.
5.1.1 Implementação
A implementação do bubblesort é bastante simples. O programa é controlado por um comando while, executado enquanto ocorrerem trocas durante uma varredura, condição esta indicada pela variável booleana troca: seu valor será verdadeiro caso haja trocas durante uma varredura, e falso caso contrário. A variável k indica a posição onde ocorreu a última troca. Assim, a varredura seguinte, se necessária, será feita somente até k.
A implementação apresentada abaixo para o mesmo vetor V (MAX = 10) não leva em consideração estes dois pontos citados: (1) parar a iteração se não houve troca e (2) só fazer as comparações até o último item trocado. Faça estas alterações no método como exercício. Coloque também dois contadores: um para a quantidade de iterações e outro para a de trocas.
procedure bubbleSort;
Var aux, i, j: integer;
Begin
for i := (MAX – 1) downto 1
do begin
for j := 1 to i
do begin
if V[j] > V[j+1]
then begin
aux := V[j];
V[j] := V[j + 1];
V[j + 1] := aux;
end;
end;
end;
end;
5.1.2 Análise do Desempenho
Consideremos duas situações extremas para o método: aquela que mais lhe favorece, e a que lhe é mais prejudicial, em termos de quantidade de operações efetuadas para ordenar um vetor de chaves.
Pelo exame de como o método procede, percebe-se que o caso mais favorável é aquele no qual as chaves já se encontram na ordem desejada. Nesses casos, ao final da primeira varredura, o método já terá descoberto que nenhuma troca foi efetuada, e que, portanto, o vetor já está ordenado. Esta primeira e única varredura demandará, pois, n- 1 comparações.
Já o caso mais desfavorável é aquele no qual as chaves se encontram na ordem inversa àquela desejada. Nesses casos, a cada varredura, apenas uma chave será depositada no seu local definitivo, enquanto as demais apenas se deslocarão uma posição para a esquerda (supondo ordenação crescente). Desse modo, as quantidades de comparações que serão efetuadas a cada varredura são as seguintes:
	Número da varredura
	Comparações efetuadas
	1
	n -1
	2
	n -2
	3
	n -3
	...
	...
	n-1
	1
O total de comparações será, pois, a soma da progressão aritmética cujo primeiro termo é n - 1 e o último é 1, com n - 1 termos, ou seja, ((n-1+1)/2 ) x (n-1) = (n2 - n)/2.
Podemos supor que, na prática, os casos que ocorram correspondam a situações intermediárias entre os extremos acima. Assim, se tomarmos a média aritmética dos valores encontrados, provavelmente estaremos fazendo uma boa estimativa do número médio de comparações que serão efetuadas.
Cmédio = (Cpior + Cmelhor) /2 = ((n² - n)/2)+ (n-1))/2 = (n² + n-2)/4
Na verdade, o número médio de comparações provavelmente será pouco menor do que isso, pois não estamos considerando, nesta análise, os possíveis blocos de chaves já ordenadas. De qualquer maneira, sendo n2 a parcela dominante, o método é de complexidade quadrática: O(n2).
5.2 Método da Agitação - Shakesort
Ao efetuarmos a análise do desempenho do método bubblesort, verificamos que a cada varredura efetuada, a maior das chaves consideradas é levada até a sua posição definitiva, enquanto que as demais se aproximam da sua posição correta de apenas uma casa. Isto sugere um aperfeiçoamento no método, no qual, ao final de uma varredura da esquerda para a direita, seja efetuada outra, da direita para a esquerda, de tal modo que, ao final desta, a menor chave também se desloque para a sua posição definitiva. Estas varreduras em direções opostas se alternariam sucessivamente, até a ordenação completa do vetor. O método resultante desta alteração do bubblesort recebeu a denominação de shakesort, já que o seu funcionamento lembra os movimentos de vaivém de uma coqueteleira. A implementação deste método é um bom exercício.
Quanto ao seu desempenho, a melhoria obtida reside apenas na quantidade de comparações efetuadas, uma vez que o método evita comparações supérfluas que o bubblesort efetua. Já o número de trocas necessárias não se altera em relação ao bubblesort. Como esta é uma operação mais onerosa do que aquela, o ganho, em tempo, não será significativo.
5.3 Método do Pente - Combsort
Um ganho significativo no bubblesort pode ser obtido usando a estratégia de promover as chaves em direção às suas posições definitivas por saltos maiores do que uma casa de cada vez. Essa alternativa, proposta por Lacey e Box, consiste em comparar não os pares consecutivos de chaves, mas pares formados por chaves que distam umas das outras uma distância h. Na primeira varredura essa distância é dada pelo valor h = n div 1,3. Nas varreduras subseqüentes, esta distância (ou salto) é novamente dividida por 1,3, até que seja igual a 1. Neste momento, o método se confunde com o bubblesort.
Cada varredura conduz as chaves para locais próximos do definitivo por meio de grandes saltos. À medida que os saltos vão diminuindo de comprimento, aproximando-se da unidade, as chaves estarão mais próximas de suas posições corretas, quando então o bubblesort se tornará eficiente.
O fator 1,3 de redução dos saltos foi obtido pelos autores do algoritmo por simulação. Foram testados
fatores que variavam de 1,1 a 1,45, sendo que o de valor 1,3 foi o que apresentou melhores resultados, em média. O estudo da seqüência de saltos, com fator de redução 1,3 revela que as possíveis seqüências de valores de h só podem terminar de uma das seguintes formas:
	9
	6
	4
	3
	2
	1
	
	10
	7
	5
	3
	2
	1
	
	11
	8
	6
	4
	3
	2
	1
O resultado das simulações revelou, também, que o terceiro caso é aquele que produz os melhores resultados. Assim, quando h>11 e o cálculo do valor do salto seguinte resultar em 9 ou 10, ele é forçado a tomar o valor 11, para que a série conclua na sua forma mais favorável ao método. A redução do tempo de classificação desse método em relação ao bubblesort tradicional (sem qualquer tipo de otimização) foi da ordem de 27 vezes.
As sucessivas reduções dos saltos são análogas ao ato de pentear cabelos longos e embaraçados, inicialmente apenas com os dedos e depois usando pentes com espaços entre os dentes cada vez menores. Daí a denominação do método dada pelos autores.
Suponhamos, para exemplo, o mesmo vetor de chaves usado para exemplificar o método bubblesort. Como o vetor possui 5 chaves, o salto inicial é igual a 3 (= 5/1.3). Como vemos, a classificação do vetor, embora também tenha consumido 9 iterações, demandou apenas três trocas, enquanto o bubblesort, para ordenar o mesmo vetor, efetuou 8 trocas. É justamente neste ponto que reside a vantagem do combsort em relação ao bubblesort, uma vez que a operação de troca, por envolver vários acessos à memória, é a que vai determinar a velocidade de classificação.
Observe na implementação que quando h=1 o método se confunde com o bubblesort.
procedure calcSalto(var h: integer);
Begin
h := h / 1.3;
if ((h = 9) or (h = 10) or (h = 11))
then h := 11;
end;
procedure combSort;
Var aux, i, salto: integer;
Begin
salto := MAX;
while (salto >= 1)
do begin
calcSalto(salto);
	for i := 1 to (MAX – salto) 
do begin
if (i + salto) <= MAX)
then begin
if V[i] > V[i + salto]
then begin
aux := V[i];
V[i] := V[i + salto];
V[i + salto] := aux;
end;
end
else break;
end;
end;
end;
5.4 Método de Partição e Troca - Quicksort
O método apresentado a seguir foi proposto por Hoare. Seu desempenho é tão melhor, que seu inventor denominou-o quicksort (ordenação rápida). De fato é o que apresenta, em média, o menor tempo de classificação. Isto porque, embora tenha um desempenho logarítmico como muitos outros, é o que apresenta menor número de operações por iteração. Isto significa que, mesmo que tenha que efetuar uma quantidade de iterações proporcional a N(log2 N), cada uma delas será mais rápida.
Seja o vetor de chaves C[1..n] a ser ordenado. Numa etapa inicial, esse vetor é particionado em três segmentos S1, S2, S3, da seguinte forma:
S2 terá comprimento 1 e conterá uma chave denominada particionadora;
S1 terá comprimento >=0 e conterá todas as chaves cujos valores forem menores ou iguais ao da chave particionadora. Esse segmento é posicionado à esquerda de S2;
S3 também terá comprimento >=0 e conterá todas as chaves cujos valores forem maiores do que o da particionadora. Esse segmento é posicionado à direita de S2.
Esquematicamente esse particionamento é mostrado nas figuras a seguir. vetor inicial: 1 
Observe que, pelo fato de:
 C[i] <= C[k] para i=1,...,k-1 e
 C[i] > C[k] para i = k+1,...,n,
a chave particionadora C[kl ocupa a sua posição correta na ordenação. O processo de particionamento é reaplicado aos segmentos S1 e S3 e a todos os segmentos correspondentes daí resultantes, que tiverem comprimento >=1. Quando não restarem segmentos a particionar, o vetor estará ordenado.
Como vemos, o método consiste na aplicação sucessiva do particionamento de segmentos, que é a operação básica do método. Assim sendo, esta operação deve ser implementada de forma simples e eficiente. Um dos pontos principais da operação é o da escolha da chave particionadora, já que o seu valor determinará o tamanho dos segmentos S1 e S3. A chave particionadora ideal é aquela que produz segmentos S1 e de igual tamanho (ou aproximado). Isto pode ser obtido se o seu valor for igual ao da chave de valor mediano. Entretanto, para encontrarmos tal chave, seria necessário percorrer todo o vetor a ser particionado. Este procedimento tornaria a operação lenta, pois deve ser aplicado a todos os segmentos de comprimento maior ou igual a um e que se formam após cada particionamento.
Para evitar isto, devemos usar um critério de escolha simples e rápido, de preferência que não envolva uma pesquisa entre as chaves. Se não tivermos nenhum conhecimento prévio sobre a distribuição dos valores das chaves, podemos supor que qualquer uma delas pode ser a particionadora; assim, com a finalidade de simplificar o algoritmo de particionamento, arbitraremos que a chave que se encontra na posição inicial do vetor a ser particionado será a particionadora. Caso tenhamos um conhecimento prévio sobre a distribuição dos valores das chaves, podemos usar um outro critério de escolha. Por exemplo, se soubermos que o vetor já se encontra parcialmente ordenado, podemos eleger como particionadora aquela chave que se encontra na posição central do vetor.
5.4.1 Exemplo do Método
O exemplo a seguir ilustra o processo de particionamento, usando a chave inicial do vetor como particionadora. O algoritmo executa o particionamento em n passos (n = número de chaves). Nos n-1 primeiros, as chaves (excluída a particionadora) são deslocadas para o lado esquerdo do vetor, se menores ou iguais à particionadora, ou para o lado direito, se maiores. No último passo a chave particionadora é inserida na sua posição definitiva correta.
Suponhamos o vetor: 9 25 10 18 5 7 15 3
Escolhemos a chave 9 como particionadora e a guardamos em uma variável temporária cp. A posição ocupada por ela se torna disponível para ser ocupada por outra chave, situação indicada por x. Marcamos também o início e o fim do vetor por dois apontadores: i (de início) e f (de fim). A expressão “esquerda” escrita ao lado do vetor indica que a posição apontada pelo ponteiro i (o da esquerda) está disponível e pode ser ocupada por outra chave. Nos passos seguintes, a expressão “direita” indica o contrário.
	
	i
	
	
	
	
	
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	1.
	x
	25
	10
	18
	5
	7
	15
	3
	esquerda
	cp=9
A seguir, comparamos a chave que está apontada por f com a particionadora. Como aquela é menor do que esta, a deslocamos para o lado esquerdo do vetor (que é o lado onde ficam as chaves menores ou iguais à particionadora), ao mesmo tempo em que avançamos o ponteiro i para indicar que a chave recém-movida já se encontra no segmento correto. A nova posição vaga passa a ser a apontada por f:
	
	
	i
	
	
	
	
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	2.
	3
	25
	10
	18
	5
	7
	15
	x
	direita
	cp=9
Agora comparamos a chave 25 (pois a nova posição vaga é a da direita) com a particionadora. Como 25 > 9, deslocamos 25 para x, e recuamos o ponteiro uma posição para a esquerda, indicando assim que a chave 25 já se encontra no seu segmento correto. Agora a posição vaga é a da esquerda:
	
	
	i
	
	
	
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	3.
	3
	x
	10
	18
	5
	7
	15
	25
	esquerda
	cp=9
O processo prossegue comparando a chave 15. Neste caso, por ela ser maior do que a particionadora, não deve ser trocada de posição, pois já se encontra no segmento correto. Apenas o ponteiro f é deslocado para a esquerda. A posição vaga permanece sendo a da esquerda:
	
	
	i
	
	
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	4.
	3
	x
	10
	18
	5
	7
	15
	25
	esquerda
	cp=9
No passo seguinte a chave 7 é colocada na posição vaga, e o ponteiro i é ajustado:
	
	
	
	i
	
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	5.
	3
	7
	10
	18
	5
	x
	15
	25
	direita
	cp=9
Os passos seguintes são feitos de forma similar e são mostrados a seguir:
	
	
	
	i
	
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	6.
	3
	7
	x
	18
	5
	10
	15
	25
	esquerda
	cp=9
	
	
	
	
	i
	f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	7.
	3
	7
	5
	18
	x
	10
	15
	25
	direita
	cp=9
O resultado do 7º passo (correspondente ao n-1) produz a situação na qual os dois ponteiros i e f se encontram. Quando isto ocorre, os segmentos S1 e S3 estão formados. A posição vaga entre eles corresponde ao segmento S2, que contém a chave particionadora cp. Assim, resta copiar cp para a posição apontada por i e j, que este passo estará completo. Observe que, embora os segmentos S1 e S3 ainda não estejam ordenados, a chave particionadora já se encontra na sua posição correta.
	
	
	
	
	i, f
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	8.
	3
	7
	5
	x=9
	18
	10
	15
	25
	cp=9
O processo de classificação prossegue com o particionamento dos segmentos S1 e S3 e todos os demais segmentos correspondentes de tamanho maior ou igual a um que forem se formando. A seqüência a seguir exibe apenas o estado final de cada processo de particionamento. As chaves particionadoras são mostradas em tipo negrito, enquanto os segmentos de apenas um elemento que se formarem são mostrados em tipo itálico.
	3
	7
	5
	9
	15
	10
	18
	25
	3
	5
	7
	9
	10
	15
	18
	25
O que encerra a ordenação do vetor.
5.4.2 Implementação
A implementação do método exigirá, portanto, a definição de dois procedimentos: um para executar uma ordenação (a que mostramos no exemplo) e outro para controlar os particionamentos. O primeiro procedimento, denominado ordenação é a seguir apresentado.
procedure Ordenacao(var inicio: inicio; fim: integer);
Var cp: integer;
 esquerda: boolean
Begin
esquerda := true;
cp := V[inicio];
while (inicio < fim)
do begin
if (esquerda)
then begin
if (cp >= V[fim]) // troca para S1 (esquerda)
then begin
V[inicio] := V[fim];
V[fim] := 0;
inicio := inicio + 1;
esquerda := false;
end
else fim := fim - 1;
end
else begin
if (cp < V[inicio]) // troca para S3 (direita)
then begin
V[fim] := V[inicio];
V[inicio] := 0;
fim:= fim - 1;
esquerda := true;
end
else inicio := inicio + 1;
end;
end;
V[inicio] := cp; // retorna a variável inicio
end;
Uma alternativa de implementação da operação de particionamento, adequada quando a chave particionadora escolhida ocupar uma posição intermediária do vetor a ser particionado e possuir um valor mediano, foi proposta por N. Wirth da seguinte forma: uma vez escolhida a chave particionadora (denominada cp), percorre-se o vetor a ser particionado da esquerda para a direita, até que seja encontrada uma chave c[i] > cp. A seguir percorre-se o vetor da direita para a esquerda, até que seja encontrada uma chave c[j] <= cp. Nesta ocasião as duas chaves c[i] e c[j] são permutadas de posição. As varreduras prosseguem a partir destes pontos, até que os dois deslocamentos se encontrem em uma posição intermediária do segmento. À esquerda ficarão as chaves menores ou iguais a cp; à direita as maiores. Observe que este processo divide o segmento em dois outros, já que a particionadora é usada apenas como referência e irá estar sempre contida no segmento da esquerda.
Falta mostrar a implementação do procedimento que irá controlar os particionamentos necessários para ordenar o vetor. Essa operação (particionamento sucessivo) é recursiva, uma vez que, obtido o primeiro particionamento, a operação é reaplicada sobre os segmentos resultantes, até que todas as partições fiquem reduzidas a um único elemento. Assim, o procedimento que implementa a operação refletirá esta natureza recursiva, sendo recursivo também:
procedure quickSort(comeco, final: integer);
Var divisor: integer;
Begin
if (final > comeco)
then begin
ordenacao(comeco, final); // devolve comeco
divisor := comeco;
quickSort(comeco, divisor – 1); // ordena segmento da direita
quickSort(divisor + 1, final); // ordena segmento da esquerda
end;
end;
Em linguagens de programação que não suportam a recursividade, a implementação do procedimento quicksort deve manipular explicitamente a pilha de pedidos pendentes de particionamento. Deixaremos a implementação dessa alternativa como exercício.
5.4.3 Análise do Desempenho
A análise feita a seguir é baseada na primeiro implementação da operação de particionamento descrita. Esta implementação, ao contrário da segunda alternativa, não efetua trocas (que implicam uma operação triangular). Cada chave encontrada fora do seu segmento é apenas transposta para a posição vaga existente. Essa operação (transposição de segmento) não será considerada na análise. Apenas consideraremos a quantidade de comparações efetuadas para decidir em que segmento deve se localizar cada uma das chaves. Como comparamos a chave particionadora com todas as demais, obviamente sempre serão requeridas n-1 comparações para particionar n chaves.
Supondo, agora, a situação ideal em que a chave particionadora seja tal que o particionamento produza dois segmentos S1 e S3 de igual tamanho, teremos dividido o vetor de n elementos em segmentos com os seguintes tamanhos:
S1 com (n - 1) /2 chaves;
S2 com 1 chave;
S3 com (n - 1)/2 chaves.
Esquematicamente:
Persistindo a situação ideal ao longo dos demais particionamentos, os segmentos que serão sucessivamente gerados terão os seguintes comprimentos:
E assim por diante, até que (n-k)/(k+1) <=1. Cada um desses segmentos vai requerer, para ser particionado, tantas comparações quantos são seus elementos menos uma unidade.
Assim, temos:
1. Para o primeiro segmento: n-1 comparações;
2. Para os 2 seguintes: (((n-1)/2)-1) x 2 = n-3 comparações;
3. Para os 4 seguintes: (((n-3)/4)-1) x 4 = n-7 comparações;
4. Para os 8 seguintes: (((n-7)/8)-1) x 8 = n-15 comparações;
e assim sucessivamente, enquanto restarem segmentos de mais de um elemento. Esta condição deixará de ocorrer após executados log2 n passos de particionamento. Logo, o total das comparações a serem efetuadas é igual à soma do número de comparações efetuadas em cada passo, ou seja:
Este seria, pois, o melhor caso para o método. Naturalmente, não devemos esperar que isto ocorra em situações normais. Supondo que as chaves sejam únicas, a probabilidade de escolhermos ao acaso exatamente a particionadora mediana é 1/n. No entanto, segundo Wirth, quando escolhemos a chave particionadora aleatoriamente, o desempenho médio do quicksort se torna inferior ao do caso ótimo de um fator da ordem de apenas 2 ln 2.
Há, ainda, a considerar o pior caso: quando a chave particionadora escolhida é a menor (ou a maior) de todas. Nesse caso, e persistindo a situação em todos os demais particionamentos, o método se torna extremamente lento, com desempenho quadrático. De fato, se a chave escolhida for sempre a menor de todas, os particionamentos produzirão os segmentos S1 vazios e os S3 com n-1 elementos, conforme o esquema mostrado adiante. Sendo necessários, pois, n-1 passos, cada um deles exigindo um número de comparações igual ao número de elementos menos um, ou seja:
(n-1) + (n-2) + (n-3) + ... + 1 = ((n-1) + 1)/2 x (n-1) = (n2 - n)/2 
Esse caso ocorrerá, por exemplo, se o vetor já estiver ordenado e sempre escolhermos a primeira chave como particionadora. Assim, quando o vetor estiver parcialmente ordenado, é conveniente usar uma chave que ocupe uma posição mais central do mesmo.
�
6	CLASSIFICAÇÃO POR SELEÇÃO
Os métodos que formam a família de classificação por seleção caracterizam-se por procurarem, a cada iteração, a chave de menor (ou maior) valor do vetor e colocá-la na sua posição definitiva correta, qual seja, no início (ou no final) do vetor, por permutação com a que ocupa aquela posição. O vetor a ser classificado fica, desta maneira, reduzido de um elemento. O mesmo processo é repetido
para a parte restante do vetor, até que este fique reduzido a um único elemento, quando então a classificação estará concluída. Os métodos de classificação por seleção diferenciam-se uns dos outros, pelo critério utilizado para selecionar, a cada iteração, a chave de menor (ou maior) valor.
6.1 Método de Seleção Direta
Neste método, a seleção da menor chave é feita por pesquisa seqüencial. Uma vez encontrada a menor chave, esta é permutada com a que ocupa a posição inicial do vetor, que fica, assim, reduzido de um elemento. O processo de seleção é repetido para a parte restante do vetor, sucessivamente, até que todas as chaves tenham sido selecionadas e colocadas em suas posições definitivas.
Suponha que se deseja ordenar o vetor: 9 25 10 18 5 7 15 3. Segundo o princípio formulado, a ordenação desse vetor de 8 chaves demandará 7 iterações, conforme mostrado na tabela a seguir.
Observe que a última iteração (7ª) encerra a classificação, pois se as n-1 menores chaves do vetor estão em suas posições definitivas corretas, então a maior (e última) automaticamente também estará.
6.1.1 Implementação
A implementação do método é direta. O procedimento a seguir toma a primeira chave da parte ainda não ordenada do vetor como sendo, em princípio, a menor de todas, comparando-a seqüencialmente com todas as demais. Sempre que encontrar uma de valor inferior, passa a considerar esta como a menor. Ao final de cada iteração, a menor chave encontrada é inserida na primeira posição da parte não classificada, que assim fica reduzida de um elemento.
procedure SelecaoDireta;
Var i, j, indX, menor: integer;
Begin
for i := 1 to (MAX -1)
do begin
menor := V[i];
indX := i;
for j := (i + 1) to MAX
do begin
if (V[j]) < menor)
then begin
menor := V[j];
indX := j;
end;
end;
V[indX] := V[i];
V[i] := menor;
end;
end;
6.1.2 Análise do Desempenho
Na análise do desempenho do método de seleção direta podemos considerar dois aspectos: a quantidade de comparações efetuadas e a quantidade de trocas de mínimos efetuadas. Quanto ao número de comparações efetuadas, temos:
1ª iteração: compara o 1º elemento com os n-1 demais: n-1 comparações.
2ª iteração: compara o 2º elemento com os n-2 demais: n-2 comparações.
3ª iteração: compara o 3º elemento com os n-3 demais: n-3 comparações.
...
(n-1)ª iteração: compara o (n-1)º elemento com o último: 1 comparação.
Total de comparações: (n-1) + (n-2) + (n-3) + ... + 1 = (n²-n)/2 = O(n²).
Observe que a quantidade de comparações efetuadas é constante para um dado n, ou seja, não depende do arranjo prévio das chaves. Já o número de trocas de mínimos durante a busca da menor chave em cada iteração não é constante, pois depende da ordem em que as chaves se apresentam. Este fato vai fazer com que os tempos de classificação de dois vetores com as mesmas chaves, porém arranjadas de formas diversas, possam ser diferentes.
Supondo que a distribuição dos valores das chaves seja uniforme, então o número médio de trocas de mínimos efetuadas ao longo de uma iteração pode ser estimado da seguinte forma: a probabilidade de que a segunda chave seja menor do que a primeira (tomada como mínimo inicial) é 1/2. A probabilidade de que a terceira chave seja menor do que as duas primeiras é 1/3. A probabilidade da quarta ser menor do que as três primeiras é 1/4 e, assim por diante, até a última chave, cuja probabilidade de ser menor do que todas as n-1 que a antecedem é 1/n. Estes valores correspondem às freqüências relativas com que cada troca vai ocorrer. Portanto, a quantidade média de trocas de mínimos durante uma iteração será: (1/2)+ (1/3) +(1/4)+ ... + (1/n), sendo n o número de chaves envolvidas na iteração.
A série de valores apresentada, acrescida da unidade, é conhecida na literatura como série harmônica, e sua soma denominada número harmônico, denotado por Hn e cujo valor, para os fins aqui propostos, pode ser aproximado por:
O símbolo y representa a constante de Euler, cujo valor é: 0,5772157...
6.2 Método da Seleção em Árvore – Heapsort
A conclusão a que chegamos sobre o método da seleção direta torna o seu uso muito restrito, pois infelizmente sempre serão necessárias n-1 comparações para decidir qual é a menor dentre n chaves. Por outro lado, essa condição só é absolutamente necessária na primeira varredura. Ao final desta, podemos reter outras informações além da identificação da menor chave, que permitam acelerar a busca das outras menores que sucedem a primeira.
Por exemplo, se dividirmos o vetor de chaves em dois segmentos de igual tamanho, poderemos, na primeira varredura, identificar a menor chave de cada segmento. A seguir, selecionaríamos a menor dentre estas duas, colocando-a na sua posição definitiva correta. Na segunda varredura será necessário operar apenas com o segmento que forneceu a menor chave, ou seja, trabalharemos com n/2 chaves ao invés de n-1, o que já representa um ganho significativo. Uma vez encontrada a segunda menor chave deste segmento, a comparamos com a do outro para selecionar a menor chave desta segunda iteração.
Este princípio pode ser estendido de modo a subdividir o vetor de chaves em tantos segmentos quantos forem possíveis, de tal forma a minimizar a quantidade de comparações a ser efetuada em cada iteração para encontrar a chave de menor valor. O quadro a seguir exemplifica a aplicação deste princípio, mostrando um vetor de chaves sucessivamente dividido ao meio, sendo a menor chave de cada segmento identificada em negrito.
A identificação da menor chave em cada um dos sucessivos segmentos nos quais o vetor foi subdividido pode ser representada pela seguinte estrutura de árvore:
Agora podemos selecionar a menor de todas as chaves e removê-la do sistema, deixando vagas as posições que ela ocupava. Essas vagas serão tomadas, por sua vez, pelas chaves sucessoras (na ordem crescente), de cada subárvore, permanecendo livre apenas a última posição anteriormente ocupada pela chave removida. Na primeira figura vemos a árvore com a chave 09 removida e, na seguinte vemos as vagas por ela deixadas ocupadas pelas chaves sucessoras.
Remoção da menor chave
Promoção da sucessora
Desse modo, a segunda menor chave aparecerá na raiz da árvore e poderá ser removida, seguindo-se a promoção da terceira menor chave, mostrada na próxima figura. Esse processo se repete até que todas as n chaves tenham sido removidas.
Promoção da terceira menor chave
Observe que, a cada nível da árvore que se desce, o problema fica reduzido pela metade, pois apenas uma subárvore é afetada pela remoção da chave. Com isso, a cada iteração, evitamos trabalhar com a totalidade das chaves restantes, o que irá acelerar bastante a seleção da menor chave em cada iteração. Este é, pois, o princípio básico do método de seleção em árvore.
6.2.1 Exemplo
A implementação do método, proposta por J. Williams, permite simplificar ainda mais a estrutura de árvore que mantém a hierarquia das chaves. A simplificação elimina a redundância de ocorrências de chaves na árvore, fazendo com que ela possua exatamente n nodos, ao invés dos 2n-1 até agora usados, o que simplifica a manipulação da estrutura. Dado então um vetor de chaves C1, C2, ... , Cn, consideramos este vetor como sendo a representação de uma árvore binária, usando a seguinte interpretação dos índices das chaves:
C1 é raiz da árvore e C2i = subárvore da esquerda de Ci, C2i+1 = subárvore da direita de Ci para i=1, n div 2.
Exemplificando: dado o vetor C1..7, e utilizando a interpretação anterior, podemos vê-lo como sendo a representação da árvore mostrada na figura:
Árvore representada pelo vetor C1..7
O passo seguinte consiste em trocar as chaves de posição dentro do vetor, de tal forma que estas passem a formar uma hierarquia, na qual todas as raízes das subárvores sejam maiores ou iguais a qualquer uma das suas sucessoras, ou seja, cada raiz deve satisfazer as seguintes condições:
Ci >=
C2i e Ci >= C2i+1 para i= 1, n div 2
Quando todas as raízes das subárvores satisfazem essas condições, dizemos que a árvore forma um heap. Daí a denominação do método.
Essas condições, na verdade, estabelecem uma relação de ordem entre as subárvores, de tal modo que, para qualquer heap, podemos afirmar que C1 >= Ci, i=2, n, ou seja, podemos afirmar que a maior chave dentre as n que formam o vetor é aquela que está na raiz da árvore, isto é, a chave C1.
O problema agora é, então, efetuar as trocas de posições das chaves no vetor, de tal forma que a árvore representada passe a ser um heap. Esse processo pode ser feito testando cada uma das subárvores para verificar se elas satisfazem, separadamente, a condição de heap. Apenas as subárvores que possuem pelo menos um sucessor devem ser testadas. A maneira mais simples de sistematizar esse teste é iniciá-lo pela última subárvore, qual seja, aquela cuja raiz está na posição n div 2 do vetor de chaves, prosseguindo, a partir daí, para as subárvores que antecedem esta, até testar a raiz da árvore.
Desse modo, a primeira subárvore da figura a ser testada é aquela cuja raiz é C3, seguindo-se o teste pela subárvore de raiz C2 e finalizando com a de raiz C1. Sempre que for encontrada uma subárvore que não forme um heap, seus componentes devem ser rearranjados de modo a formar o heap. Por exemplo, se for encontrada uma subárvore como a da figura (a), seus componentes devem ser rearranjados na forma da figura (b).
Transformação de uma subárvore em heap
Pode ocorrer também que, ao rearranjarmos uma subárvore, isto venha a afetar outra, do nível imediatamente inferior, fazendo com que esta deixe de formar um heap. Essa possibilidade obriga a verificar, sempre que for rearranjada uma subárvore, se a sucessora do nível abaixo não teve a sua condição de heap desfeita. Para exemplificar todo o processo, suponhamos o seguinte vetor de chaves:
	1
	2
	3
	4
	5
	6
	7
	12
	09
	13
	25
	18
	10
	22
cuja interpretação sob a forma de árvore é:
A transformação dessa árvore em heap inicia pela subárvore cuja raiz é 13, já que seu índice, no vetor, é 7 div 2 = 3. O rearranjo dos componentes desta subárvore produz a configuração da árvore e do vetor correspondente mostrada na figura:
Transformação da subárvore de raiz 13 em heap
A próxima subárvore a ser rearranjada é a de raiz 09, mostrada na figura:
Transformação da subárvore de raiz 09 em heap
E finalmente a de raiz 12, na figura abaixo.
Transformação da subárvore de raiz 12 em heap
Nesse caso ocorreu a possibilidade mencionada, na qual a transformação de uma subárvore afeta outra de um nível abaixo. A subárvore afetada deve ser rearranjada, conforme mostra a figura abaixo.
Rearranjo de uma subárvore do nível inferior
Uma vez que todas as subárvores formam heaps, a árvore toda também é um heap. Até aqui se conseguiu apenas selecionar a maior chave que aparece na raiz da árvore. Entretanto, a partir deste ponto, em vista da configuração tomada pela árvore, a seleção das chaves seguintes será simplificada. 
Se a chave que está na raiz é a maior de todas, então sua posição definitiva correta na ordem crescente é na última posição do vetor, onde ela é colocada, por troca com a chave que ocupa aquela posição. Com a maior chave ocupando a sua posição definitiva podemos, a partir de agora, considerar o vetor como tendo um elemento a menos, o qual será mostrado no vetor (área sombreada), mas não aparecerá na árvore correspondente, conforme ilustrado na figura a seguir.
Colocação da maior chave em sua posição definitiva
Para selecionar a próxima chave, deve-se fazer com que a árvore volte a ser um heap. Como a única subárvore que sofreu alterações foi a da raiz, basta fazer com que esta subárvore volte a formar um heap, rearranjando-se os seus componentes, e verificando-se, também, se este rearranjo não interferiu em uma das subárvores do nível imediatamente abaixo.
Seleção da segunda maior chave
Novamente a maior chave dentre as restantes aparece na raiz (perceba a pequena quantidade de comparações necessárias para efetuar a seleção desta chave). A figura abaixo mostra a segunda maior chave sendo colocada em sua posição definitiva correta, de forma idêntica ao do caso anterior.
Colocação da segunda maior chave em sua posição
Na figura seguir a árvore é novamente rearranjada para formar um heap, o que permitirá selecionar a próxima chave.
Seleção da terceira maior chave
Os demais passos seguem o mesmo princípio e são mostrados na figura a seguir. Da mesma forma que no caso da seleção direta, a classificação estará encerrada após a iteração n-1, pois teremos selecionado as n-1 maiores chaves, restando apenas a menor de todas, que estará na posição inicial do vetor, o que encerra a classificação.
Final do processo de classificação
6.2.2 Implementação
O algoritmo que implementa esse método segue exatamente a descrição anterior. Para simplificar a manipulação do vetor, foi criada uma função auxiliar keyval, que retorna o valor da chave que está na posição i do vetor, caso i <= n. Em caso contrário, o valor da função será igual a minkey, que corresponde ao menor valor de chave possível de ser representado. Por exemplo, se as chaves forem do tipo inteiro de 16 bits, então minkey será igual a -215 = -32768. O uso dessa função nos permitirá não fazer distinção entre nodos raízes e folhas, assegurando o término natural do processamento.
/* baseado em algoritmo de [Aze 96], Pg 59 */
function keyval(n, i: integer): integer;
begin
if (i > n)
then return := MINKEY
else return := V[i];
end;
Com auxílio de keyval, escrevemos o procedimento heap, cuja finalidade é transformar em heap a subárvore cuja raiz é apontada por r. Para cada subárvore transformada, é verificado se a subárvore do nível inferior que esteve envolvida na transformação não foi afetada. Em caso afirmativo, a verificação também se estende a ela. O processo se encerra quando não houver mais trocas, ou quando for atingido o nível das folhas da árvore.
/* baseado em algoritmo de [Aze 96], Pg 60 */
procedure heap(n, r: integer);
var i, h, r, aux: integer;
 troca: boolean;
begin
i := r;
troca := true;
while troca
do begin
// procura maior subárvore
if (keyVal(n, 2*i) > keyVal(n, 2*i+1))
then h := 2 * i // subárvore da esquerda
else h := 2 * i + 1; // subárvore da direita
if (V[i] < keyVal(n, h)) // compara raiz com o maior sucessor
then begin
aux := V[i]; // troca
V[i] := V[h];
V[h] := aux;
i := h; // desce para a raiz da subárvore afetada pela troca
end
else troca := false; 
end;
end;
Resta agora o procedimento final, que denominaremos heapsort. Este será constituído de duas partes. A primeira fará a formação do heap inicial: preparará a árvore para a seleção da maior chave. A segunda parte, que denominaremos manutenção do heap, rearranjará a árvore após cada seleção da maior chave, para que ela retome a forma de heap, permitindo assim a seleção da próxima chave. Essa segunda parte demanda n-1 iterações, e corresponde à fase de classificação propriamente dita.
/* baseado em algoritmo de [Aze 96], Pg 61 */
procedure heapSort(n: integer);
var i: integer;
 troca: boolean;
begin
i := n div 2; // raiz da última árvore
for r := i downto 1 // formação do heap inicial
do heap(n, r);
for n1 := (n-1) downto 1 // manutenção do heap
do begin
aux := V[i]; // troca
V[i] := V[n1+1];
V[n1+1] := aux;
heap(n1, 1); // refaz heap a partir da raiz da árvore
end;
end;
6.2.3 Análise do Desempenho
Na análise do desempenho do heapsort, devemos considerar separadamente as duas fases do método: a formação do heap inicial e a sua manutenção. Para a fase de formação, a situação mais favorável ao método é aquela na qual as chaves já satisfazem as condições Ci >= C2i e Ci >= C2i+1, para i=1, n div 2. Uma permutação que satisfaz essas condições é a do vetor na ordem decrescente,

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes