Ordenacao - Aed II c Pas

Universidade Regional Integrada do Alto Uruguai e das Missões - URI Fundação Regional Integrada – FuRI

Campus de Frederico WestphalenDepartamento de Engenharias e Ciência da Computação

Curso de Ciência da Computação

Algoritmos e Estrutura de Dados II

Leandro Rosniak TibolaE-mail: [email protected]

Página Pessoal: www.fw.uri.br/~tibola

1

Sumário1 Introdução...................................................................................................................................................4

1.1 Tipos Abstratos de Dados...................................................................................................................41.2 Objetivos da Estrutura de Dados.........................................................................................................41.3 Estruturas de Dados Homogêneas.......................................................................................................4

1.3.1 Matrizes de Uma Dimensão ou Vetores......................................................................................41.3.2 Matrizes com Mais de Uma Dimensão........................................................................................7

2 Listas Lineares..........................................................................................................................................102.1 Fundamentos.....................................................................................................................................102.2 Formas de Armazenamento...............................................................................................................11

2.2.1 Alocação Estática versus Dinâmica...........................................................................................112.2.2 Alocação Seqüencial..................................................................................................................122.2.3 Alocação Encadeada..................................................................................................................13

3 Pilhas.........................................................................................................................................................153.1 Organização de Dados na pilha.........................................................................................................16

3.1.1 Declarando uma pilha................................................................................................................163.1.2 Inicializando uma pilha.............................................................................................................163.1.3 Verificando limites da pilha......................................................................................................173.1.4 Inserindo elementos na pilha.....................................................................................................173.1.5 Removendo elementos na pilha.................................................................................................183.1.6 Verificando o elemento do topo da pilha...................................................................................20

4 Filas...........................................................................................................................................................224.1 Implementação Seqüencial de Filas..................................................................................................23

4.1.1 Declarando uma fila...................................................................................................................234.1.2 Inicializando uma fila................................................................................................................234.1.3 Verificando limites da fila.........................................................................................................244.1.4 Inserindo elementos na fila........................................................................................................244.1.5 Removendo elementos da fila....................................................................................................264.1.6 Problemas na Implementação Seqüencial de Filas....................................................................27

4.2 Solucionando os Problemas da Implementação Seqüencial.............................................................274.3 Implementação Circular para Filas...................................................................................................28

4.3.1 Declarando e inicializando uma fila..........................................................................................284.3.3 Verificando limites da fila.........................................................................................................294.3.4 Inserindo elementos na fila........................................................................................................294.3.5 Removendo elementos da fila....................................................................................................30

5 Classificação por Inserção........................................................................................................................335.1 Método da Inserção Direta................................................................................................................33

5.1.1 Exemplo de Inserção Direta......................................................................................................335.1.2 Implementação...........................................................................................................................345.1.3 Análise do Desempenho............................................................................................................345.3.1 Exemplo Incrementos Decrescentes - Shellsort........................................................................375.3.2Implementação............................................................................................................................385.3.3Análise do Desempenho.............................................................................................................38

6 Classificação por Trocas...........................................................................................................................396.1 Método da Bolha - Bubblesort.........................................................................................................39

6.1.1 Exemplo.....................................................................................................................................39

2

6.1.2 Implementação...........................................................................................................................406.1.3 Análise do Desempenho............................................................................................................40

6.2 Método da Agitação - Shakesort.......................................................................................................416.3 Método do Pente - Combsort............................................................................................................42

6.3.1 Exemplo.....................................................................................................................................426.3.2 Implementação...........................................................................................................................43

6.4 Método de Partição e Troca - Quicksort...........................................................................................436.4.1 Descrição do Método.................................................................................................................446.4.2 Implementação...........................................................................................................................466.4.3 Análise do Desempenho............................................................................................................47

7 Classificação por Seleção..........................................................................................................................507.1 Método de Seleção Direta.................................................................................................................50

7.1.1 Exemplo.....................................................................................................................................507.1.2 Implementação...........................................................................................................................507.1.3Análise do Desempenho.............................................................................................................517.2.1 Implementação...........................................................................................................................547.2.2 Análise do Desempenho............................................................................................................61

7.3 Método de Seleção em Árvore Amarrada - Threadedheapsort.........................................................618 Classificação por Distribuição de Chaves.................................................................................................65

8.1 Método de Indexação Direta - Radixsort..........................................................................................668.1.1 Desempenho..............................................................................................................................70

9 Classificação por Intercalação..................................................................................................................719.1 Método da Intercalação Simples - Mergesort...................................................................................71

9.1.1 Implementação...........................................................................................................................729.1.2 Análise do Desempenho............................................................................................................74

10 Listas Ordenadas.....................................................................................................................................7610.1 Implementação Encadeada para Listas Ordenadas.........................................................................76

10.1.1 A Operação de Inserção...........................................................................................................7710.1.2 A operação de Remoção..........................................................................................................7910.1.3 A Operação de Pesquisa..........................................................................................................8010.1.4 Imprimindo uma Lista Ordenada.............................................................................................8110.1.5 Destruindo uma Lista Ordenada..............................................................................................81

10.2 Técnicas de Encadeamento.............................................................................................................8210.2.1 Nodos Cabeça e Sentinela.......................................................................................................82

10.3 Encadeamento circular....................................................................................................................8510.4 Encadeamento Duplo..................................................................................................................87

Bibliografia..................................................................................................................................................89

3

1 IntroduçãoNeste capítulo são apresentados os conceitos fundamentais para o entendimentos das

estruturas de dados abordados na apostila. Para sincronização com a disciplina de Linguagemde Programação II, nos quatro primeiros capítulos serão usados exemplos tanto na linguagemPascal quanto na linguagem C e nos capítulos seguintes na linguagem C.

1.1 Tipos Abstratos de DadosUm tipo abstrato de dados é formado por um conjunto de valores e por uma série de

operações que podem ser aplicadas sobre ele. Operações e valores, em conjunto, constituemum modelo matemático que pode ser empregado para modelar e solucionar problemas domundo real.

Para que possamos realmente aplicar um modelo matemático na resolução deproblemas por computador, é preciso antes transformá-lo num tipo de dados concreto, ousimplesmente tipo de dados.

A transformação de um tipo de dados abstrato em um tipo de dados concreto échamada implementação. É durante o processo de implementação que a estrutura dearmazenamento dos valores é especificada, e que os algoritmos que desempenharão o papeldas operações são projetados.

1.2 Objetivos da Estrutura de DadosO estudo das estruturas de dados envolve dois objetivos complementares:

� Teórico: identificar e desenvolver modelos matemáticos, determinando que classes deproblemas podem ser resolvidos com o uso deles.

� Prático: criar representações concretas de objetos e desenvolver rotinas capazes de atuarsobre estas representações, de acordo com o modelo considerado.

O primeiro objetivo considera um tipo abstrato de dados como um recurso a serempregado durante a resolução de problemas em geral; e o segundo considera aimplementação deste tipo abstrato de dados como um problema em si, que pode ser resolvidoatravés do uso de outros tipos de dados já disponíveis, possivelmente predefinidos nalinguagem escolhida para a implementação.

1.3 Estruturas de Dados HomogêneasAs estruturas de dados homogêneas permitem agrupar diversas informações dentro de

uma mesma variável. Este agrupamento ocorrerá obedecendo sempre ao mesmo tipo de dado,e é por esta razão que estas estruturas são chamadas homogêneas.

A utilização deste tipo de estrutura de dados recebe diversos nomes, como: variáveisindexadas, variáveis compostas, variáveis subscritas, arranjos, vetores, matrizes, tabelas emmemória ou arrays. Os nomes mais usados e que utilizaremos para estruturas homogêneassão: matrizes (genérico) e vetores (matriz de uma linha e várias colunas).

1.3.1 Matrizes de Uma Dimensão ou Vetores

Este tipo de estrutura em particular é também denominado por profissionais da áreacomo matrizes unidimensionais. Sua utilização mais comum está vinculada à criação detabelas. Caracteriza-se por ser definida uma única variável vinculada dimensionada com um

4

determinado tamanho. A dimensão de uma matriz é constituída por constantes inteiras epositivas. Os nomes dados às matrizes seguem as mesmas regras de nomes utilizados paraindicar as variáveis simples.

A sintaxe do comando de definição de vetores é a seguinte, em Pascal:var<nome_da_variável> : array [ <coluna_inicial> .. <coluna_final> ] of <tipo_de_dado>;Exemplo:varM : array [1 .. 10] of integer;

A sintaxe do comando de definição de vetores é a seguinte, em C :<tipo_de_dado> <nome_da_variável> [ <valor> ];Exemplo em C:int M [10] ; int m [10] ; char Numero [5]; float numero [12];

� Operações Básicas com Matrizes do Tipo VetorDo mesmo modo que acontece com variáveis simples, também é possível operar com

variáveis indexadas (matrizes). Contudo não é possível operar diretamente com o conjuntocompleto, mas com cada um de seus componentes isoladamente.

O acesso individual a cada componente de um vetor é realizado pela especificação desua posição na mesma por meio do seu índice. No exemplo anterior foi definida uma variável Mcapaz de armazenar 10 número inteiros. Para acessar um elemento deste vetor deve-sefornecer o nome do mesmo e o índice do componente desejado do vetor (um número de 1 a10, no caso do Pascal e um número de 0 à 9 no caso do C).

Para Pascal, por exemplo, M[1] indica o primeiro elemento do vetor, M[2] indica osegundo elemento do vetor e M[10] indica o último elemento do vetor.

Já, para C, M[0] indica o primeiro elemento do vetor, M[1] indica o segundo elementodo vetor e M[9] indica o último elemento do vetor.

Portanto, não é possível operar diretamente sobre vetores como um todo, mas apenassobre seus componentes, um por vez. Por exemplo, para somar dois vetores é necessáriosomar cada um de seus componentes dois a dois. Da mesma forma as operações deatribuição, leitura e escrita de vetores devem ser feitas elemento a elemento.

� Atribuição de Uma Matriz do Tipo VetorTendo como base as instruções primitivas, o comando de atribuição ode ser definido

como:Pascal:<nome_da_variável> [ <índice> ]:= <expressão>C:<nome_da_variável> [ <índice> ] = <expressão>No caso de vetores (variáveis indexadas), além do nome da variável deve-se

necessariamente fornecer também o índice do componente do vetor onde será armazenado oresultado da avaliação da expressão.

Em Pascal temos o comando 'M[1] = 12;' enquanto em C seria 'M[0] := 12;'.

5

� Leitura de Dados de Uma Matriz do Tipo VetorA leitura de um vetor é feita passo a passo, um de seus componentes por vez, usando

a mesma sintaxe da instrução primitiva da entrada de dados, onde além do nome da variável,deve ser explicitada a posição do componente lido:

Pascal:read ( <nome_da_variável> [ <índice> ] );read ( M[1] );C:scanf (''%i'', &<nome_da_variável> [ <índice> ] );scanf( “%i” , &M[0]);Uma observação importante a ser feita é a utilização da construção ''for'' a fim de

efetuar a operação de leitura repetidas vezes, em cada uma delas lendo um determinadocomponente do vetor. De fato esta construção é muito comum quando se opera com vetores,devido à necessidade de se realizar uma mesma operação com os diversos componentes dosmesmos. Na verdade, são raras as situações que se deseja operar isoladamente com um únicocomponente do vetor.

� Escrita de Dados de Uma Matriz do Tipo VetorA escrita de um vetor obedece à mesma sintaxe da instrução primitiva de saída de

dados e também vale lembrar que, além do nome do vetor, deve-se também especificar pormeio do índice o componente a ser escrito:

Pascal:write ( <nome_da_variável> [ <índice> ] );Ex.: write (M[1]);C:printf (''%i'', <nome_da_variável> [ <índice> ] );Ex.: printf(“%i” , M[0]);

� Remoção de Dados de Uma Matriz do Tipo VetorPara a remoção de dados de um vetor deve observar uma regra: não podemos tornar

vazia uma posição de um vetor que já tenha sido utilizada. Ela será vazia, para nosso uso, nomomento de sua criação, contendo, mesmo assim, um valor relativo a posição de memóriautilizada, variando sua conteúdo de linguagem para linguagem. Para termos certeza de queseu conteúdo está dentro do conjunto com qual queremos trabalhar, podemos atribuir um valornulo ao inicializar a variável, assim:

Pascal:<nome_da_variável> [ <índice> ] := <valor_nulo>C:<nome_da_variável> [ <índice> ] = <valor_nulo>

� Exemplos de Aplicação de VetoresO espectro de aplicação de vetores em algoritmos é muito extenso, mas normalmente

os vetores são usados em duas tarefas muito importantes no processamento de dados:pesquisa e classificação.

6

A pesquisa consiste na verificação da existência de um valor dentro de um vetor.Trocando em miúdos, pesquisar um vetor consiste em procurar dentre seus componentes umdeterminado valor.

A classificação de um vetor consiste em arranjar seus componentes numadeterminada ordem, segundo um critério específico. Por exemplo, este critério pode ser aordem alfabética de um vetor de dados caracter, ou então a ordem crescente ou decrescentepara um vetor de dados numéricos. Há vários métodos de classificação, mas o mais conhecidoé o método da bolha de classificação (Bubble Sort).

1.3.2 Matrizes com Mais de Uma Dimensão

Este tipo de estrutura também tem sua principal utilização vinculada à criação detabelas. Caracteriza-se por ser definida uma única variável vinculada dimensionada com umdeterminado tamanho. A dimensão de uma matriz é constituída por constantes inteiras epositivas. Os nomes dados às matrizes seguem as mesmas regras de nomes utilizados paraindicar as variáveis simples.

A sintaxe do comando de definição de matrizes de duas dimensões é a seguinte:Pascal:var <nome_da_variável> : array [<linha_inicial> .. <linha_final> , <coluna_inicial> ..

<coluna_final> ] of <tipo_de_dado> ;Ex.:varm : array [1 .. 5 , 1 .. 10] of integer;C:<tipo_de_dado> <nome_da_variável> [<nro_linhas> ] [<nro_colunas> ] ;Ex.: int valor [5] [10];

Também é possível definir matrizes com várias dimensões, por exemplo:Exemplo em Pascal:

varN : array [1 .. 4] of integer;O : array [1 .. 4 , 1 .. 50 ] of integer;P : array [1 .. 4, 1 .. 50 , 1 .. 5] of integer;Q : array [1 .. 4, 1 .. 50 , 1 .. 5 , 1 .. 3 ] of integer;R : array [1 .. 4, 1 .. 50 , 1 .. 5 , 1 .. 3 , 1 .. 2 ] of integer;S : array [1 .. 4, 1 .. 50 , 1 .. 5 , 1 .. 3 , 1 .. 2 , 1 .. 2 ] of integer;

Exemplo em C: int N [4];int O [4] [50];int P [4] [50] [5];int Q [4] [50] [5] [3];int R [4] [50] [5] [3] [2];int S [4] [50] [5] [3] [2] [2];

7

A utilidade de matrizes desta forma é muito grande. No exemplo acima, cada matrizpode ser utilizada para armazenar uma quantidade maior de informações:

.a matriz N pode ser utilizada para armazenar 4 notas de um aluno.

.a matriz O pode ser utilizada para armazenar 4 notas de 50 alunos.

.a matriz P pode ser utilizada para armazenar 4 notas de 50 alunos de 5 disciplinas.

.a matriz Q pode ser utilizada para armazenar 4 notas de 50 alunos de 5 disciplinas, de3 turmas.

.a matriz R pode ser utilizada para armazenar 4 notas de 50 alunos de 5 disciplinas, de3 turmas, de 2 colégios.

.a matriz S pode ser utilizada para armazenar 4 notas de 50 alunos de 5 disciplinas, de3 turmas, de 2 colégios, de 2 cidades.

� Operações Básicas com Matrizes de Duas DimensõesDo mesmo modo que acontece com os vetores, não é possível operar diretamente com

o conjunto completo, mas com cada um de seus componentes isoladamente.O acesso individual a cada componente de uma matriz é realizado pela especificação

de sua posição na mesma por meio do seu índice. No exemplo anterior foi definida umavariável 'O' capaz de armazenar 50 número inteiros em cada uma das 4 linhas. Para acessarum elemento desta matriz deve-se fornecer o nome da mesma e o índice da linha e da colunado componente desejado da matriz (um número de 1 a 4 para a linha e um número de 1 a 50para a coluna, neste caso).

Em Pascal, por exemplo, O[1,1] indica o primeiro elemento da primeira linha da matriz,O[1,2] indica o segundo elemento da primeira linha da matriz, O[1,50] indica o último elementoda primeira linha da matriz e O[4,50] indica o último elemento da última linha da matriz

Da mesma forma como vetores, não é possível operar diretamente sobre matrizescomo um todo, mas apenas sobre seus componentes, um por vez. Por exemplo, para somarduas matrizes é necessário somar cada um de seus componentes dois a dois. Da mesmaforma as operações de atribuição, leitura e escrita de matrizes devem ser feitas elemento aelemento.

� Atribuição de Uma Matriz de Duas DimensõesNa atribuição de matrizes, da mesma forma que nos vetores, além do nome da variável

deve-se necessariamente fornecer também o índice do componente da matriz onde seráarmazenado o resultado da avaliação da expressão. O índice referente ao elemento écomposto por tantas informações quanto o número de dimensões da matriz. No caso de terduas dimensões, o primeiro número se refere à linha e o segundo número se refere à coluna damatriz em que se encontra a informação:

Pascal:<nome_da_variável> [ <linha> , <coluna> ] := <expressão>Ex.: m[1,1] := 15 ; m[1,10] := 10 ; m[3,5] := 20 ; m[5,10] := 35 ;C:<nome_da_variável> [ <linha> ] [ <coluna> ] = <expressão>Ex.: m[1][1] = 15 ; m[1][10] = 10 ; m[3] [5] = 20 ; m[5][10] = 35 ;

8

� Leitura de Dados de Uma Matriz de Duas DimensõesA leitura de uma matriz é feita passo a passo, um de seus componentes por vez,

usando a mesma sintaxe da instrução primitiva da entrada de dados, onde além do nome davariável, deve ser explicitada a posição do componente lido:

Pascal:read ( <nome_da_variável> [ <índice_1>, ... , < índice_n> ] );Ex.: read ( O [2,4] );C: scanf (''%i'', &<nome_da_variável> [ <índice_1> ] [ .. ] [ <índice_n> ] );Ex.: scanf(“%i” , &O[2][4]);Uma observação importante a ser feita é a utilização de construções Para aninhadas

ou encadeada a fim de efetuar a operação de leitura repetidas vezes, em cada uma delas lendoum determinado componente da matriz. Esta construção é muito comum quando se opera commatrizes, devido à necessidade de se realizar uma mesma operação com os diversoscomponentes das mesmas.

� Escrita de Dados de Uma Matriz de Duas DimensõesA escrita de uma matriz obedece à mesma sintaxe da instrução primitiva de saída de

dados e também vale lembrar que, da mesma forma que com vetores, além do nome da matriz,deve-se também especificar por meio do índice o componente a ser escrito:

Pascal:write ( <nome_da_variável> [ <índice_1> , ... , <índice_n> ] );Ex.: write ( O [2,4] );C: printf (''%i'', <nome_da_variável> [ <índice_1> ] [ .. ] [ <índice_n> ] );

Ex.: print (“%i” , O[2] [4]);

9

2 Listas LinearesUma 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 listados amigos que participarão da festa? As listas têm-se mostrado um recurso bastante útil eeficiente no dia-a-dia das pessoas. Em computação, não tem sido diferente: a lista é uma dasestruturas de dados mais empregadas no desenvolvimento de programas.

2.1 FundamentosUma 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 = 0dizemos 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 deordem unidimensional dos elementos que a compõem. Uma ordem que nos permite dizer comprecisã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 aosextremos da lista, temos casos especiais que aparecem muito freqüentemente na modelagemde problemas a serem resolvidos por computador. Tais casos especiais recebem tambémnomes 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/First-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çõese 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 qualquerextremo. Filas Duplas são também denominadas DEQUE (Double-Ended QUEue), ou emportuguê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 deSaída Restrita (se a remoção for restrita a um único extremo).

10

2.2 Formas de ArmazenamentoAo 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 aoarmazenamento dos dados. Quem determina quanto de memória será usado para asinstruçõ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 quatrocategorias apresentadas a seguir:

Seqüencial Encadeada

Estática Estática Seqüencial Estática Encadeada

Dinâmica Dinâmica Seqüencial Dinâmica EncadeadaFigura 2.1: Tipos de alocação de memória.

2.2.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 totalde memória utilizada pelos dados é previamente conhecida e definida de modo imutável, nopróprio código-fonte do programa. Durante toda a execução, a quantidade de memória utilizadapelo programa não varia. Por outro lado, se o programa é capaz de criar novas variáveisenquanto 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 nada mais é que uma área de memória, dizemos quesua alocação é estática se sua existência já era prevista no código do programa; de outraforma, dizemos que sua alocação é dinâmica.

A seguir, vemos o uso de variável estática em contraste com variável dinâmica:

{ Alocação: mostra uso de variáveis estáticas X dinâmicas em Pascal}program alocacao;type ptr = ^integer;varP: ptr; {aloca variável estaticamente}beginnew(P); {aloca variável dinamicamente}P^ := 12345;writeln(P^);end.

{ Alocação: mostra uso de variáveis estáticas X dinâmicas em C}# include <stdio.h># include <string.h># include <stdlib.h># include <conio.h>

int var_int, *pt_int;char var_char, *pt_char;float var_float, *pt_float;

int main(){

11

pt_int = (int *) malloc(sizeof(int));pt_char = (char *) malloc(sizeof(char));pt_float= (float *) malloc(sizeof(float));

var_int = 8 ; *pt_int = 9 ;var_char = 'a' ; *pt_char = 'A' ;var_float = 2.2 ; *pt_float = 3.3 ;

printf("<<< Variaveis estaticas e dinamicas >>>\n");printf("var_int : %i\n", var_int);printf("var_char : %c\n", var_char);printf("var_float: %f\n", var_float);printf("\nvalor - posicao\n");printf("*pt_int : %i - &pt_int : %p\n", *pt_int, &pt_int);printf("*pt_char : %c - &pt_char : %p\n", *pt_char, &pt_char);printf("*pt_float: %f - &pt_float: %p\n", *pt_float, &pt_float);

free(pt_int);free(pt_char);free(pt_float);

scanf("%c",&var_char);return(0);}

Figura 2.2: Alocação estática e dinâmica.

Olhando para o texto do programa 'alocação', identificamos a presença das variáveisvar_int, var_char e var_float. Dizemos, portanto, que estas são variáveis alocadasestaticamente (cuidado para não confundir este conceito de variável estática/dinâmica comaquele de variável estática/automática existente em linguagens como ''C'').

Entretanto, observando a figura 2.2, que representa a memória no momento daexecuçã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ãoconhecemos seu nome, temos apenas seu endereço!), como é o caso das variáveis pt_int,pt_char e pt_float.

Em C, as variáveis dinâmicas são alocadas através de diversos comandos, entre eles ocomando malloc(). Este comando recebe como argumento o número de bytes de memória aserem alocados, verifica se existe uma área dc memória disponível e, se existir, aloca estaárea. Para liberar uma área previamente alocada pelo comando malloc(), usamos o comandofree().

Os atributos seqüencial e encadeada só fazem sentido se a memória considerada forarmazenar uma coleção de objetos, como é o caso da memória necessária para armazenaruma lista linear, e serão discutidos a seguir.

2.2.2 Alocação Seqüencial

A forma mais natural de armazenar uma lista dentro do computador consiste emcolocar os seus elementos em células de memória consecutivas, um após outro. Assim, secada célula tem um endereço único E e utiliza k bytes, temos:

12

memória usada pelo programa

P : 1FFA

Endereço

1FFA12345

memória livre no sistema

E-k E E+k... ai-1 ai ai+1 ...

kFigura 2.3: Esquema de alocação seqüencial.

� 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 nacélula de endereço B, temos a equação: Endereço(ai ) = B + (i-1)k.

B+0k B+1k B+2k B+(i-1)k B+(i-1)k... a1 a2 a3 ... ai an ...

kFigura 2.4: Esquema de acesso seqüencial.

A maior vantagem no uso de uma área seqüencial de memória para armazenar umalista linear é que, dado o endereço inicial B da área alocada e o índice i de um elementoqualquer da lista, podemos acessá-lo imediatamente, com um simples e rápido cálculo. Oponto fraco desta forma de armazenamento aparece quando precisamos inserir ou suprimirelementos do meio da lista, quando então um certo esforço será necessário para movimentaros elementos, de modo a abrir espaço para inserção, ou de modo a ocupar o espaço liberadopor um elemento que foi removido.

2.2.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 ocuparquaisquer células (não necessariamente consecutivas) e, para manter a relação de ordemlinear, 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 dememória denominados nodos, sendo que cada nodo é composto por dois campos: um paraarmazenar dados e outro para armazenar endereço.

Dois endereços especiais devem ser destacados (como visto na figura 2.5):� 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 ouremover elementos do meio da lista. Como os elementos não precisam estar armazenados emposições consecutivas de memória, nenhum dado precisa ser movimentado, bastando atualizaro campo de ligação do elemento que precede aquele inserido ou removido. Por exemplo, pararemover o elemento a2 da lista representada na figura 2.5, basta mudar o nodo no endereço3FFA de (a1,1C34) para (a1,BD2F). Como apenas o primeiro elemento é acessível diretamenteatravés do endereço L, a grande desvantagem da alocação encadeada surge quandodesejamos acessar uma posição específica dentro da lista. Neste caso, levemos partir doprimeiro 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.

13

Endereço ConteúdoL=3FFA a1 1C34 Primeiro elemento, acessível a partir de L

1C34 a2 BD2F Note que o segundo elemento não ocupa um endereçoconsecutivo àquele ocupado por a1

BD2F a3 AC12... ... ...

1000 ai 3A7B Cada nodo armazena um elemento e o endereço dopróximo elemento da lista

... ... ...5670 an-2 14F614F6 an-1 5D4A5D4a an nil Último elemento da cadeia, o endereço nulo (nil)

indica que o elemento an , não tem um sucessorFigura 2.5: Esquema de alocação encadeada.

14

3 PilhasA 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 oprimeiro 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 suaexistência. O nome pilha advém justamente da semelhança entre o modo como as listas LIFOcrescem e diminuem e o modo como as pilhas, no mundo real, funcionam. O exemplo maiscomum do quotidiano é uma pilha de pratos, onde o último prato colocado é o primeiro a serusado (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 otamanho da pilha P , acrescentando o elemento x no seu topo. A operação Pop ( P ) faz comque a pilha diminua, removendo e retornando o elemento existente em seu topo. Das trêsoperações básicas, a única que não altera o estado da pilha é Top ( P ); ela simplesmenteretorna uma cópia do elemento existente no topo da pilha sem removê-lo.

Exercício 1: Dadas as operações sobre uma pilha P, preencha o quadro a seguir comestado da pilha e o resultado de cada operação:

Operação Estado da Pilha Resultado– P: [] –

Push (P, 10) P: [ 10 ] –Push (P, 15) P: [ 10, 15 ] -

Pop ( P ) P: [ 10 ] 15Top ( P ) P: [ 10 ] 10Pop ( P )

Push ( P, 5)Push ( P, 8)

Pop ( P )Push ( P, 13)

Top ( P )Pop ( P )Pop ( P )

Push ( P, 3 )Top ( P )

15

3.1 Organização de Dados na pilhaComo 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 dealocação seqüencial de memória mostra-se bastante apropriado para implementá-las. Nesteesquema, 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.

Nota que vetor é o mecanismo oferecido pelas linguagen de programação nos premitealocar, de forma estática, uma área seqüencial de memória, e o índice é o recurso necessáriopara disciplinar o acesso aos elementos da pilha.

3.1.1 Declarando uma pilha

Para declarar uma pilha, precisamos então de duas variáveis: um vetor com o tamanhonecessário para armazenar as informações e uma variável que indica o topo, como no exemploabaixo, que implementa uma pilha de tamanho máximo igual a 10:

Pascal:Program Pilha;

const MAX = 10;VarV: Array[1..MAX] of integer;topo: integer;

C:#include <conio.h>#include <stdio.h>#include <stdlib.h>

#define MAX 10

int pilha[MAX];char x[5]; int topo;...

3.1.2 Inicializando uma pilha

Para inicializar uma pilha, deve-se “inicializar” o topo (no caso do C, usar um valorabaixo da primeira posição útil do vetor, que é a posição 0 - zero):

Pascal:Program Pilha;

const MAX = 10;

varV: array[1..MAX] of integer;topo: integer;

begintopo := 0;...

C:#include <conio.h>#include <stdio.h>

16

#include <stdlib.h>

#define MAX 10

int pilha[MAX];char x[5]; int topo, op, nro, i;

int main(){topo :=-1; op=0; nro=0; i=0;

...

3.1.3 Verificando limites da pilha

Uma inserção só pode ser feita na pilha se o topo for menor que o seu tamanhomáximo, caso contrário ocorre o que se chama de estouro de pilha ou stack overflow.

Da mesma forma, uma retirada da pilha 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 tamanhomáximo. O teste para verificar se pode ser feita uma inserção numa pilha que tem tamanhomáximo igual a 10 é mostrado no exemplo abaixo:

Pascal:if topo = MAX then

beginwriteln('Pilha cheia!');end;

C:if ( topo == MAX-1 )

printf("\nOverflow - pilha cheia !!!") ;

Para verificar se uma pilha está vazia, basta testar se o topo é inferior a zero. O testepara verificar se pode ser feita uma retirada é mostrado no exemplo abaixo:

Pascal:if topo = 0 then

beginwriteln('Pilha vazia!');end;

C:if ( topo == -1 )

printf("\nUnderflow - pilha vazia !!!");

3.1.4 Inserindo elementos na pilha

Para inserir um elemento na pilha, precisamos saber qual é o elemento a ser inserido etestar se a pilha está cheia. Se a mesma não está cheia, incrementamos o topo e na posiçãodo topo inserir o novo elemento. O exemplo abaixo ilustra a inserção de um elemento na pilha:

Pascal:Program Pilha;Uses Crt;

const MAX = 10;

Var

17

V: Array[1..MAX] of integer;topo: integer;x: integer;

Begintopo := 0;write('Valor a inserir: ');readln (x);if topo = MAX then

beginwriteln('Pilha cheia!');end

elsebegintopo := topo + 1;V[topo] := x;end;

...end.


#define MAX 10

int pilha[MAX];char x[5];int topo, op, nro, i;

int main(){topo=-1 ; op=0; nro=0; i=0;do

{clrscr();printf("\n1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Consultar topo\n");printf("4 - Mostrar pilha\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);if (op == 1 )

{printf("\nDigite um numero inteiro e positivo: ");scanf("%d",&nro);if ( topo == MAX-1 )

printf("\nOverflow - pilha cheia !!!") ;else

{topo++;pilha[topo] = nro;printf("\nO valor %d foi inserido na posicao %

d",nro,topo);}

fflush(stdin);gets(x);}

...

3.1.5 Removendo elementos na pilha

Para remover um elemento na pilha, precisamos saber se a pilha não está vazia. Se amesma não está vazia, mostra-se o valor que está no vetor na posição apontada pelo topo edecrementa-se o topo. O exemplo abaixo ilustra a remoção de um elemento da pilha:

18


const MAX = 10;

VarV: Array[1..MAX] of integer;topo: integer;x: integer;




if topo = 0 thenbeginwriteln('Pilha vazia!');end

elsebeginwriteln('O valor retirado é: ', V[topo]);topo := topo - 1;end;

end.


#define MAX 10


int main(){topo=-1; op=0; nro=0; i=0;do

{clrscr();printf("\n1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Consultar topo\n");printf("4 - Mostrar pilha\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);if (op == 1 )

{printf("\nDigite um numero inteiro e positivo: ");scanf("%d",&nro);if ( topo == MAX-1 )



d",nro,topo);

19

}fflush(stdin);gets(x);}

if ( op == 2 ){if ( topo == -1 )

printf("\nUnderflow - pilha vazia !!!");else{topo-- ;printf("\nValor %d retirado com sucesso.",pilha[topo+1] ) ;}fflush(stdin);gets(x);}

3.1.6 Verificando o elemento do topo da pilha

Para verificar o elemento que está no topo da pilha, precisamos saber se a pilha nãoestá vazia. Se a mesma não está vazia, mostra-se o valor que está no vetor na posiçãoapontada pelo topo sem decrementar o topo. O exemplo abaixo ilustra a verificação doelemento que está no topo da pilha:


const MAX = 10;

VarV: Array[1..MAX] of integer;topo: integer;x: integer;




if topo = 0 thenbeginwriteln('Pilha vazia!');end

elsebeginwriteln('O valor que está no topo é: ', V[topo]);end;

end.

C: #include <conio.h>#include <stdio.h>#include <stdlib.h>

#define MAX 10


20

int main(){topo=-1; op=0; nro=0; i=0;

do{clrscr();printf("\n1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Consultar topo\n");printf("4 - Mostrar pilha\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);

if (op == 1 ){printf("\nDigite um numero inteiro e positivo: ");scanf("%d",&nro);if ( topo == MAX-1 )



d",nro,topo);}


if ( op == 2 ){if ( topo == -1 )

printf("\nUnderflow - pilha vazia !!!");else{topo-- ;printf("\nValor %d retirado com sucesso.",pilha[topo+1] ) ;}fflush(stdin);gets(x);}

if ( op == 3 ){if ( topo == -1 )

printf("\nImpossivel mostrar o topo, a pilha estavazia.");

elseprintf("\nValor %d no posicao %d .",pilha[topo],topo);


ExercíciosUtilizando procedimentos e/ou funções, fazer um programa em Pascal ou C que

manipule uma pilha. O programa deve ter um menu principal com as seguintes opções:1 - Inserir elementos na pilha2 - Retirar elementos na pilha3 - Verificar o elemento que está no topo da pilha4 - Mostrar todos os elementos da pilha.5 - Sair

21

4 FilasUma fila é um tipo especial de lista linear em que as inserções são realizadas em um

extremo, ficando as remoções restritas ao outro. O extremo onde os elementos são inseridos édenominado final da fila, e aquele de onde são removidos é denominado começo da fila.

Cada vez que uma operação de inserção é executada, um novo elemento écolocado no final da fila. Na remoção, é sempre retornado o elemento que aguarda há maistempo na fila, ou seja, aquele posicionado no começo. A ordem de saída correspondediretamente à ordem de entrada dos elementos na fila, de modo que os primeiros elementosque entram são sempre os primeiros a sair. Por este motivo, as filas são denominadas listasFIFO (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, ondepessoas formam uma fila para aguardar até serem atendidas. Naturalmente, devemosdesconsiderar 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 nemremoção no meio da lista.

Figura : 4.1: Funcionamento de uma fila.

A palavra queue, da língua inglesa, significa fila. Por tradição, as operações básicasque 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 otamanho da fila F , acrescentando o elemento x no seu final. A operação Dequeue ( F ) fazcom que a fila diminua, removendo e retornando o elemento existente em seu começo.

Exercício 1: Dadas as operações sobre uma fila F, preencha o quadro a seguir comestado da fila e o resultado de cada operação:

Operação Estado da Fila Resultado– F: [ ] –Enqueue ( F, 10 ) F: [ 10 ] –Enqueue ( F, 15 ) F: [ 10, 15 ] -Dequeue ( F ) F: [ 15 ] 10Enqueue ( F, 5 )Enqueue ( F, 8 )Dequeue ( F )Enqueue ( F, 13 )Dequeue ( F )Dequeue ( F )Enqueue ( F, 21 )Enqueue ( F, 50 )Dequeue ( F )Dequeue ( F )Dequeue ( F )

22

O O O O O O O O O O O O O O O O O O O O O o o o o o o o

Final

Saída <=

Começo

<= Entrada

4.1 Implementação Seqüencial de FilasGraficamente, 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:

Figura 4.2: Representação gráfica de uma fila F:[a, b, c, d]

A partir da representação gráfica percebemos que é possível implementar uma filatendo três recursos básicos:� espaço de memória para armazenas os elementos (um vetor);� uma referência ao primeiro elemento da coleção (uma variável);� uma referência à primeira posição livre, após o último elemento da fila (uma variável).

4.1.1 Declarando uma fila

Para declarar uma fila, precisamos então de três variáveis: um vetor com o tamanhonecessário para armazenar as informações; uma variável que indica o começo da fila e umavariável que indica o final da fila, como no exemplo abaixo, que implementa uma fila detamanho máximo igual a 10:

Pascal:Program Fila;

const MAX = 10;

VarV: Array[1..MAX] of integer;comeco, final : integer;

C:#include <stdio.h>#include <stdlib.h>#include <conio.h>

#define MAX 10

int fila[MAX];char x[5];

4.1.2 Inicializando uma fila

Para inicializar uma fila, deve-se atribuir o valor 1 às variáveis que controlam o começo eo final da fila:


const MAX = 10;

VarV: Array[1..10] of integer;comeco, final : integer;

23

...dcba

Começo Final

F:

Begincomeco := 1;final := 1;...


#define MAX 10


int main(){int inicio=0, fim=0, op=0, nro=0, i=0;

4.1.3 Verificando limites da fila

Uma inserção só pode ser feita na fila se a fila não estiver cheia (final for menor que oseu tamanho máximo). Da mesma forma, uma retirada da fila só pode ser feita se existemelementos na fila (o começo for diferente do final).

Para verificar se uma fila está cheia, basta testar se o final é maior que o seu tamanhomáximo. O teste para verificar se pode ser feita uma inserção numa fila que tem tamanhomáximo igual a 10 é mostrado no exemplo abaixo:

Pascal:if final > MAX then

beginwriteln('Fila cheia!');end;

C: if (fim == MAX)

printf("Overflow - fila cheia !!!") ;

Para verificar se uma fila está vazia, basta testar se o começo é igual ao final. O testepara verificar se pode ser feita uma retirada é mostrado no exemplo abaixo:

Pascal:if comeco = final then

beginwriteln('Fila vazia!');end;

C:if (inicio == fim)

printf("Underflow - fila vazia !!!");

4.1.4 Inserindo elementos na fila

Para inserir um elemento na fila, precisamos saber qual é o elemento a ser inserido etestar se a fila está cheia. Se a mesma não está cheia, o elemento é inserido na posiçãoapontada pela variável final, que deve ser incrementada depois da inserção. O exemplo abaixoilustra a inserção de um elemento na fila:

24


const MAX = 10;

VarV: Array[1..MAX] of integer;comeco, final : integer;x: integer;

Begincomeco := 1;final := 1;write('Valor a inserir: ');readln (x);if final > MAX then

beginwriteln('Fila cheia!');end

elsebeginV[final] := x;final := final + 1end;

...end.

C: #include <stdio.h>#include <stdlib.h>#include <conio.h>

#define MAX 10



do{clrscr();printf("\n<<< Fila >>> \n");printf("1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Mostrar fila\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);if ( op == 1 )

{if (fim == MAX)

printf("Overflow - fila cheia !!!") ;else

{printf("Digite um numero inteiro e positivo: ");scanf("%d",&nro);fila[fim]=nro;fim++;printf("O valor %d foi inserido na posicao %

d",nro,fim);}fflush(stdin);gets(x);

}

25

4.1.5 Removendo elementos da fila

Para remover um elemento da fila, precisamos saber se a fila não está vazia. Se amesma não está vazia, mostra-se o valor que está no vetor na posição apontada pelo comecoe incrementa-se o começo. O exemplo abaixo ilustra a remoção de um elemento da fila:


const MAX = 10;

VarV: Array[1..MAX] of integer;comeco, final : integer;x: integer;

Begincomeco := 1;final := 1;write('Valor a inserir: ');readln (x);if final > MAX then


elsebeginV[final] := x;final := final + 1end;

if comeco = final thenbeginwriteln('Fila vazia!');end

elsebeginwriteln('O valor retirado é: ', V[comeco]);comeco := comeco + 1;end;

end.


#define MAX 10



do{clrscr();printf("\n<<< Fila >>> \n");printf("1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Mostrar fila\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);

if ( op == 1 ){

26

if (fim == MAX)printf("Overflow - fila cheia !!!") ;

else{printf("Digite um numero inteiro e positivo: ");scanf("%d",&nro);fila[fim]=nro;fim++;printf("O valor %d foi inserido na posicao %

d",nro,fim);}fflush(stdin);gets(x);

}

if ( op == 2 ){if (inicio == fim)

printf("Underflow - fila vazia !!!");else

{fila[inicio]=0;inicio++;printf("Valor retirado com sucesso.") ;}fflush(stdin);gets(x);

}

4.1.6 Problemas na Implementação Seqüencial de Filas

Vimos que cada vez que um elemento é removido, o índice que aponta o começo dafila desloca-se uma posição à direita (incrementado). Supondo que a fila tenha um tamanhomáximo de 10, após 10 inserções o ponteiro que aponta para o final da fila tem o valor 11 e afila estará cheia, pois o final maior que o tamanho máximo representa fila cheia, não podendoser inserido mais nenhum elemento. Após 10 retiradas, o ponteiro que aponta para o começoda fila terá o valor 11 e a fila estará vazia, pois o começo igual ao final representa fila vazia.

Resumindo, chegamos a uma situação extremamente indesejável. Temos uma filacheia e vazia ao mesmo tempo. Afinal como isto é possível? Chegamos à conclusão de queesta nossa implementação não é muito eficiente, apresentando tanto desperdício de memóriaquanto problemas de lógica.

4.2 Solucionando os Problemas da Implementação SeqüencialEliminar o erro lógico, que sinaliza fila vazia e cheia ao mesmo tempo, é bastante

simples. Basta acrescentar uma variável contadora para indicar quantos elementos estãoarmazenados na fila. Esta variável deve ser inicialmente zerada. Quando um elemento forinserido, ela será incrementada; quando for removido, ela será decrementada. Desta forma, oimpasse pode ser resolvido simplesmente consultando essa variável.

Para eliminar o desperdício de memória, o ideal seria que cada posição liberada porum elemento removido se tornasse prontamente disponível para receber um novo elementoinserido. Para isso teríamos de dispor de uma área seqüencial de memória tal que a posição 1estivesse imediatamente após a última posição. Assim, a fila somente estaria cheia, quandorealmente tivesse um elemento para cada posição.

27

Figura 4.2: Representação de uma fila circular.

4.3 Implementação Circular para FilasA partir da representação gráfica percebemos que é possível implementar uma fila

circular tendo quatro recursos básicos:� espaço de memória para armazenas os elementos (um vetor);� uma referência ao primeiro elemento da coleção (uma variável);� uma referência à primeira posição livre, após o último elemento da fila (uma variável);� um indicador da quantidade de elementos da fila.

4.3.1 Declarando e inicializando uma fila

Para declarar uma fila, precisamos então de quatro variáveis: um vetor com o tamanhonecessário para armazenar as informações; uma variável que indica o começo da fila; umavariável que indica o final da fila e uma variável que indica a quantidade de elementos na fila,como no exemplo abaixo, que implementa uma fila de tamanho máximo igual a 10 e inicializaseus respectivos valores, :

Pascal:Program FilaCircular;

const MAX = 10;

VarV: Array[1..MAX] of integer;qtd, comeco, final : integer;

Begincomeco := 1;final := 1;qtd := 0;...


const MAX=10;

void main(){int inicio=0, fim=0, qtd=0, fila[MAX];int op=0, nro=0;

28

a

b

Final e d

c

Começo

5 4

3

2

1

...

char x[5];

4.3.3 Verificando limites da fila

Uma inserção só pode ser feita na fila se a fila não estiver cheia, (se a quantidade deelementos for menor que a quantidade máxima). Da mesma forma, uma retirada da fila só podeser feita se existem elementos na fila (se a quantidade de elementos for maior que zero).

Para verificar se uma fila está cheia, basta testar se a variável contadora é igual ao seutamanho máximo. O teste para verificar se pode ser feita uma inserção numa fila que temtamanho máximo igual a 10 é mostrado no exemplo abaixo:

Pascal:if qtd = MAX then

beginwriteln('Fila cheia!');end;

C: if (qtd == MAX)

printf("Overflow - fila cheia !!!") ;

Para verificar se uma fila está vazia, basta testar se o começo é igual ao final. O testepara verificar se pode ser feita uma retirada é mostrado no exemplo abaixo:

Pascal:if qtd = 0 then

beginwriteln('Fila vazia!');end;

C: if (qtd == 0)

printf("Underflow - fila vazia !!!");

4.3.4 Inserindo elementos na fila

Para inserir um elemento na fila, precisamos saber qual é o elemento a ser inserido etestar se a fila está cheia. Se a mesma não está cheia, o elemento é inserido na posiçãoapontada pela variável final, que deve ser incrementada depois da inserção. O exemplo abaixoilustra a inserção de um elemento na fila:

Pascal:Program FilaCircular;

const MAX = 10;

VarV: Array[1..MAX] of integer;qtd, comeco, final : integer;x: integer;

Begincomeco := 1;final := 1;qtd := 0;write('Valor a inserir: ');readln (x);if qtd = MAX then

beginwriteln('Fila cheia!');

29

endelse

beginV[final] := x;qtd := qtd + 1;if final = MAX then

beginfinal := 1 ;end

elsebeginfinal := final + 1;end;

end;...end.


const MAX=10;

void main(){int inicio=0, fim=0, qtd=0, fila[MAX];;int op=0, nro=0;char x[5];

do{clrscr();printf("1 - Inserir\n");printf("2 - Retirar\n");printf("3 - Mostrar fila\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);

if ( op == 1){if (qtd == MAX)


{printf("Digite um numero inteiro e positivo: ");scanf("%d",&nro);fila[fim]=nro;qtd++;

if (fim == MAX-1)fim=0;

elsefim++;

printf("O valor %d foi inserido.",nro);}fflush(stdin);gets(x);

}

4.3.5 Removendo elementos da fila

Para remover um elemento da fila, precisamos saber se a fila não está vazia. Se amesma não está vazia, mostra-se o valor que está no vetor na posição apontada pelo comecoe incrementa-se o começo. O exemplo abaixo ilustra a remoção de um elemento da fila:e

30

Pascal: Program FilaCircular;

const MAX = 10;

VarV: Array[1..10] of integer;qtd, comeco, final : integer;x: integer;

Begincomeco := 1; final := 1;qtd := 0;write(?Valor a inserir: ?);readln (x);if qtd = MAX then


elsebeginV[final] := x;qtd := qtd + 1;if final = MAX then

beginfinal := 1 ;end

elsebeginfinal := final + 1end;

end;if qtd = 0 then

beginwriteln('Fila vazia!');end

elsebeginwriteln('O valor retirado é: ', V[comeco]);qtd := qtd - 1;if comeco = MAX then

begincomeco := 1 ;end

elsebegincomeco := comeco + 1; end;

end;end.


const MAX=10;

void main(){int inicio=0, fim=0, qtd=0, fila[MAX];;int op=0, nro=0;char x[5];

do{clrscr();printf("1 - Inserir\n");

31

printf("2 - Retirar\n");printf("3 - Mostrar fila\n");printf("9 - Sair\n");printf("Escolha uma opcao -> ");scanf("%d", &op);

if ( op == 1){if (qtd == MAX)


{printf("Digite um numero inteiro e positivo: ");scanf("%d",&nro);fila[fim]=nro;qtd++;

if (fim == MAX-1)fim=0;

elsefim++;

printf("O valor %d foi inserido.",nro);}fflush(stdin);gets(x);

}

if ( op == 2 ){if (qtd == 0)

printf("Underflow - fila vazia !!!");else

{fila[inicio]=0;qtd--;

if (inicio == MAX-1)inicio = 0;

elseinicio++;

printf("Valor retirado com sucesso.") ;}fflush(stdin);gets(x);

}

ExercíciosUtilizando procedimentos e/ou funções, fazer um programa em Pascal ou C que

manipule uma fila de nomes de alunos. O programa deve ter um menu principal com asseguintes opções:

1 - Inserir alunos na fila2 - Retirar alunos da fila3 - Apresentar todos os alunos da fila4 - Sair

32

5 Classificação por InserçãoA classificação por inserção é caracterizada pelo princípio no qual os n dados a serem

ordenados são divididos em dois segmentos: um já ordenado e outro a ser ordenado. Nummomento inicial, o primeiro segmento é formado por apenas um elemento, que, portanto, podeser considerado como já ordenado. O segundo segmento é formado pelos restantes n-1elementos. A partir daí, o processo se desenvolve em n-1 iterações, sendo que em cada umadelas um elemento do segmento não ordenado é transferido para o primeiro segmento, sendoinserido 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 formacomo localizam a posição relativa em que cada elemento deve ser inserido no segmento jáordenado.

5.1 Método da Inserção DiretaNeste 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 partirdo primeiro e, por busca seqüencial realizada da direita para a esquerda no segmento jáordenado, localiza-se a sua posição relativa correta.

À cada comparação realizada entre o elemento a ser inserido e os que lá já seencontram, podemos obter um dos seguintes resultados:� a)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 queanteriormente ocupava.

� b)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 à suaposição relativa correta no segmento já ordenado.

Caso o elemento a ser inserido seja maior do que todos, a inserção corresponde adeixá-lo na posição que já ocupava.

Após a inserção, a fronteira entre os dois segmentos é deslocada uma posição para adireita, indicando, com isto, que o segmento ordenado ganhou um elemento e o não ordenadoperdeu um. O processo prossegue até que todos os elementos do segundo segmento tenhamsido inseridos no primeiro.

5.1.1 Exemplo de Inserção DiretaTabela 5.1 – Exemplo do método de inserção direta.

vetor original 18 15 7 9 23 16 14divisão inicial 18 15 7 9 23 16 14

Ordenado não ordenadoprimeira iteração 15 18 7 9 23 16 14segunda iteração 7 15 18 9 23 16 14terceira iteração 7 9 15 18 23 16 14quarta iteração 7 9 15 18 23 16 14quinta iteração 7 9 15 16 18 23 14sexta iteração 7 9 14 15 16 18 23(vetor ordenado)

33

void insercao_direta(void){int aux,i,j;

for ( j=1; j<MAX; j++){aux=vetor[j];i=j-1;while ((i>=0) && (vetor[i]>aux))

{vetor[i+1]=vetor[i];i--;}

vetor[i+1]=aux;}

}

5.1.2 Implementação

A implementação acima demonstra estritamente a descrição formulada: o segmento jáordenado é percorrido da direita para a esquerda, até que seja encontrada uma chave menorou igual àquela que está sendo inserida, ou até que o segmento termine . Enquanto nenhumadessas condições ocorrer, as chaves comparadas vão sendo deslocadas uma posição para adireita. 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 pelosdeslocamentos , avançando-se, a seguir, a fronteira entre os dois segmentos . O processo todoé completado em n-1 iterações.

5.1.3 Análise do Desempenho

O desempenho do método da inserção direta é fortemente influenciado pela ordeminicial das chaves a serem ordenadas. Isto se deve principalmente ao fato de que as chavesque já estão no vetor ordenado, e que são maiores do que a que está sendo inserida, devemser transpostas uma posição para a direita, para dar lugar àquela que vai ser inserida. Observeque, mesmo se usássemos um método de busca mais eficiente do que a linear, nãoevitaríamos a operação de transposição.

A situação mais desfavorável para o método é aquela em que o vetor a ser ordenadose apresenta na ordem contrária à desejada. Isto significa que cada elemento a ser inseridosempre será menor do que todos os que já estão no segmento ordenado. Isto acarreta umdeslocamento de todos eles uma posição para a direita.

A tabela a seguir mostra a quantidade de comparações e transposições necessáriaspara inserir cada uma das chaves:

Tabela 5.2 – Quantidade de comparações e transposições para cada chave.1ª chave : 12ª chave : 23ª chave : 3... chave : ...

(n-1)ª chave : n-1O total corresponderá à soma dos números de operações efetuadas em cada iteração:

1+2+3+...+(n—1), que é igual à soma dos termos de uma progressão aritmética cujo primeirotermo é 1 e o último é (n -1):

S = ( 1 + (n+1) ) / 2 * (n - 1) = (n² - n) / 2.

34

Por outro lado, o melhor caso para o método é aquele no qual as chaves já seapresentam 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. Dequalquer maneira, é necessária pelo menos uma comparação para localizar a posição dachave.

Logo, nesta situação, o método efetuará um total de n-1 iterações para dar o vetorcomo ordenado.

Podemos supor que em situações normais o vetor não se apresente já ordenado, nemtampouco com a ordenação inversa àquela desejada. E razoável imaginarmos uma situaçãointermediária entre os casos extremos, supondo que esta corresponda à média aritmética entreos dois casos.

Assim, o desempenho médio do método é dado por:( (n - 1) + ( (n² - n) / 2 ) ) / 2 = (n² + n - 2) / 4 = � (n²)Podemos também usar uma outra abordagem para estimarmos 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 dechaves fora do lugar.

Para cada caso, consideramos dois tipos de comparações: as necessárias paradescobrir a posição correta das chaves que estão fora do seu lugar, e as necessárias paradescobrir 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, mesmoque o vetor se apresente na ordem inversa àquela desejada, podemos considerar que pelomenos uma chave se encontra na sua posição correta, enquanto as n-1 demais se encontramdeslocadas.

A Tabela 5.3 mostra a quantidade de comparações necessárias em cada caso. Acoluna A indica a quantidade de chaves fora do seu local. A coluna B mostra o número decomparações efetuadas para descobrir o local correto de cada chave que está fora do seulugar. Já a coluna C exibe o número de comparações para descobrir que as demais chavesestão no seu local correto.

Tabela 5.3 - Quantidade de comparações efetuadas em cada caso.A B C0 0 n – 11 n / 2 n – 22 2 * n / 2 n – 33 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çõesindicadas 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 piorcaso do método, também respectivamente, na análise efetuada anteriormente.

35

Considerando, como antes, que o caso médio corresponde à média aritmética entre omelhor e o pior caso, temos:

número médio de chaves fora do local = ( 0 + (n - 1)) / 2 = (n—1) / 2nú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.

5.2 Inserção Direta com Busca BináriaComo 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 deveser inserida no segmento ordenado. Isto não nos livra, no entanto, da necessidade deefetuarmos os deslocamentos das chaves que são maiores do que aquela que está sendoinserida, para lhe dar lugar.

Eventualmente poderíamos pensar em organizar o segmento ordenado sob a forma deuma lista encadeada, de tal forma a evitar a necessidade de deslocamentos. A inserção seriafeita apenas com ajustes de ponteiros. Mas, por outro lado isto nos obrigaria a uma pesquisaseqü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, ficaremos ainda com o ônusdos elevados tempos de deslocamento.

Supondo, no entanto, que mesmo assim optemos por esta solução, vejamos então qualo seu comportamento.

Sabemos que o número de comparações necessárias para localizar a posição que umelemento 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 kvariando de 1 até n-1.

Restam as operações de deslocamento que, como já sabemos, são realizadas emquantidades proporcionais ao quadrado do número de chaves.

Sugerimos, como exercício, que demonstre que o número médio de deslocamentosnecessários para inserir as n-1 chaves é (n² - n)/4.

Vemos, assim, que a alternativa de usar a pesquisa binária para rapidamente encontrara posição de inserção não produz grandes ganhos no desempenho do método, pois após alocalização, ainda é necessário promover os deslocamentos das chaves à direita da posição deinserção, que é uma operação de desempenho Ο(n²). Caso, no entanto, possamos dispor deuma arquitetura que execute deslocamentos em blocos, poderemos obter vantagens no tempodespendido com a operação.

Deixamos ainda a sugestão de implementar o método de classificação por inserçãocom busca binária, comparando-o com o de busca seqüencial.

5.3 Método dos Incrementos Decrescentes - ShellsortEste 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 e/ouestas já possuem uma ordenação parcial.

De fato, como o desempenho do método é quadrático, se dividirmos o vetor em hsegmentos, de tal forma que cada um possua aproximadamente n/h chaves e classificarmoscada segmento separadamente, teremos, para cada um deles, um desempenho em torno de(n/h)2. Para classificarmos 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 aproximemmais do arranjo final, isto é, teremos feito uma ordenação parcial do vetor, o que contribui para

36

a diminuição da complexidade do método.Para implementar o método, o vetor C[1..n] é dividido em segmentos, assim formados:

Tabela 5.4 –Divisão em segmentos no método dos Incrementos Decrescentes.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. Inicialmente consideraremos incrementos iguais a potênciasinteiras de 2.

Num primeiro passo, para um certo h inicial, os segmentos assim formados são entãoclassificados por inserção direta.

Num segundo passo, o incremento h é diminuído (a metade do valor anterior, se esteera uma potência inteira de 2), dando origem a novos segmentos, os quais também serãoclassificados por inserção direta.

O processo se repete até que h=1. Quando for feita uma classificação com h=1, o vetorestará 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çõesparciais do vetor, o que favorece o desempenho dos passos seguintes, uma vez que a inserçãodireta é acelerada quando o vetor já se encontra parcialmente ordenado (veja mais, em relaçãoa desempenho, em Método de Inserção Direta).

5.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élulapertence.

Primeiro passo: h = 41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 25 49 12 18 23 45 38 53 42 27 13 11 28 10 141 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4Após classificar cada um dos quatro segmentos, o vetor terá o aspecto a seguir.Segundo passo: h = 21 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1611 23 10 12 17 25 27 13 18 28 45 14 53 42 49 38Após classificar cada um dos dois segmentos, o vetor terá o aspecto seguinte:Terceiro (e último) passo: h = 11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1610 12 11 13 17 14 18 23 27 25 45 28 49 38 53 421 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Após a execução do último passo, o vetor resultará classificado:P1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1610 11 13 13 14 17 18 23 25 27 28 38 42 45 49 53

37

5.3.2Implementação

A implementação do método dos incrementos decrescentes corresponde a umaadaptação da implementação do método de inserção direta, de tal forma que, ao invés declassificar um vetor cujos elementos se encontram contíguos uns aos outros, considera apenasos elementos do vetor que pertencem a um certo segmento, ou seja, os elementos que iniciamnuma dada célula f e estão espaçados entre si a uma distância h. A seguir são mostradas asadaptações que devem ser efetuadas no procedimento inserção direta. As setas indicam aslinhas que foram alteradas. O resultado é o procedimento inserção direta shell.

void shell_sort(void){int i, j, k, salto, aux;int a[5] = {9,5,3,2,1}; // intervalosfor(k=0; k<5; k++)

{salto = a[k];for(i=salto; i<MAX; i++)

{aux = vetor[i];for(j=i-salto; aux<vetor[j] && j>=0; j=j-salto)

vetor[j+salto] = vetor[j];vetor[j+salto] = aux;}

}}

5.3.3Análise do Desempenho

Segundo Knuth e Wirth, a análise do desempenho do método é muito complexa, poisidentifica 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 produznos passos subseqüentes. Também não se conhece exatamente a melhor seqüência deincrementos que produz o melhor resultado. A este respeito, observa-se que os valores dosincrementos não podem ser múltiplos uns dos outros. Isto evitará que se combine, em umaiteraçã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 aplicadauma 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 resultadosobtidos foram com as seguintes seqüências de incrementos:

Tabela 5.5: Resultados para incrementos no shellsort.1,09 n1,27 para a série 2k +1,...,9,5,3,1; = ...,2,1 1,22 n1,26 para a série 2k - l,...,15,7,3,l; k= ...,2,11,12 n1,28 para a série (2k - (-1) k) / 3,...,11,5,3,1; k= ...,3,21,66 n1,25 para a série (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.

38

6 Classificação por TrocasOs 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 nopar.

6.1 Método da Bolha - BubblesortNeste 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.

6.1.1 Exemplo

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 dasmesmas. O processo de comparação dos n-1 pares de chaves é denominado de varredura. Ométodo efetuará tantas varreduras no vetor quantas forem necessárias para que todos ospares 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 depares de chaves, executando mais uma varredura. Observe, no entanto, que a primeiravarredura sempre irá posicionar a chave de maior valor na sua posição definitiva correta (nofinal do vetor). Isto significa que na segunda varredura podemos desconsiderar a últimaposição do vetor, que portanto fica reduzido de um elemento. Esta situação se repetirá ao finalde 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

39

concluído.Examinando-se o comportamento do método, vemos que eventualmente, dependendo

da disposição das chaves, uma certa varredura pode colocar mais do que uma chave na suaposição definitiva. Isto ocorrerá sempre que houver blocos de chaves já previamenteordenadas, 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çãodefinitiva. Isto significa que a próxima varredura não precisa ignorar apenas a última chave. Asquatro últimas podem ser ignoradas. A quantidade de chaves, a partir da última, que pode serignorada 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 deum fluido. Cada bolha teria um diâmetro proporcional ao valor de uma chave. Assim, as bolhasmaiores subiriam com velocidades maiores, o que faria com que, após um certo tempo, elas searranjassem em ordem de tamanho.


A implementação do método bubblesort é bastante simples, não exigindo nenhumgrande artifício. O programa é controlado por um comando while, que é executado enquantoocorrerem trocas durante uma varredura. Esta condição é indicada pela variável booleanatroca. Seu valor será verdadeiro, caso haja trocas durante uma varredura, e falso, casocontrário. Assim, o comando while será executado enquanto esta variável for verdadeira, ouseja, enquanto houver trocas.

A variável k indica a posição onde ocorreu a última troca. Assim, a varredura seguinte,se necessária, será feita somente até aquela posição.

void bubble_sort(void){int i, j, aux;for(i = MAX - 1; i > 0; i--)

for(j = 0; j < i; j++)if(vetor[j] > vetor[j+1])

{aux = vetor[j];vetor[j] = vetor[j+1];vetor[j+1] = aux;}

}

6.1.3 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 ordenarum 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. De fato, nesses casos, ao finalda primeira varredura, o método já terá descoberto que nenhuma troca foi efetuada, e que

40

portanto, o vetor já se encontra ordenado. Esta primeira e única varredura demandará, pois, n-1 comparações.

Já o caso mais desfavorável será aquele no qual as chaves se encontram na ordeminversa àquela desejada. Nesses casos, a cada varredura, apenas uma chave será depositadano seu local definitivo, enquanto as demais apenas se deslocarão uma posição para aesquerda (supondo ordenação crescente). Desse modo, as quantidades de comparações queserão efetuadas a cada varredura são as seguintes:

Tabela 6.1: Número de comparações efetuadas por varredura (bubblesort)Nº da varredura Comparações efetuadas

1 n – 12 n – 23 n – 3... ...

n – 1 1

O total de comparações será, pois, a soma da progressão aritmética cujo primeirotermo é 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çõesintermediárias entre os extremos acima. Assim, se tomarmos a média aritmética dos valoresencontrados, provavelmente estaremos fazendo uma boa estimativa do número médio decomparações que serão efetuadas.

Cmédio = (Cpior + Cmelhor) /2 = ((n² - n)/2)+ (n-1))/2 = (n² + n-2)/4Na 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 complexidadequadrática.

6.2 Método da Agitação - ShakesortAo 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çãodefinitiva, 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 esquerdapara 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 emdireçõ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 deshakesort, 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 decomparações efetuadas, uma vez que o método evita muitas das comparações supérfluas queo bubblesort efetua. Já o número de trocas necessárias não se altera em relação aobubblesort. Como esta é uma operação mais onerosa do que aquela, o ganho, em tempo, nãoserá significativo.

41

6.3 Método do Pente - CombsortUm ganho significativo no método 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 apenasuma casa de cada vez. Essa alternativa, proposta por Lacey e Box, consiste em comparar nãoos pares consecutivos de chaves, mas pares formados por chaves que distam umas das outrasuma certa distância h. Na primeira varredura essa distância é dada pelo valor h = n div 1,3. Nasvarreduras subseqüentes, esta distância (também denominada salto) é progressivamentediminuída do fator 1,3, até que seja igual a unidade. Neste momento, o método se confundecom o bubblesort tradicional.

Cada varredura rapidamente conduz as chaves para locais próximos do definitivo pormeio de grandes saltos. A medida que os saltos vão diminuindo de comprimento, aproximando-se da unidade, as chaves estarão já bem próximas de suas posições corretas, quando então obubblesort 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 queapresentou melhores resultados, em média.

O estudo da seqüência de saltos, com fator de redução 1,3 revela que as possíveisseqüências de valores de h só podem terminar de uma das seguintes formas:

9 6 4 3 2 110 7 5 3 2 111 8 6 4 3 2 1

O resultado das simulações revelou, também, que o terceiro caso é aquele que produzos melhores resultados. Assim, quando h>11 e o cálculo do valor do salto seguinte resultarem9 ou 10, ele é forçado a tomar o valor 11, para que a série conclua na sua forma mais favorávelao método.

A redução do tempo de classificação desse método em relação ao bubblesorttradicional (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 eembaraçados, inicialmente apenas com os dedos e depois usando pentes com espaços entreos dentes cada vez menores. Daí a denominação do método dada pelos autores.

6.3.1 Exemplo

Suponhamos o mesmo vetor de chaves usado para exemplificar o método bubblesort.Como o vetor possui 5 chaves, o salto inicial é igual a 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 8trocas. É justamente neste ponto que reside a vantagem do combsort em relação aobubblesort, uma vez que a operação de troca, por envolver vários acessos à memória, é a quevai determinar a velocidade de classificação.

42

Tabela 6.2: Número de comparações efetuadas por varredura (combsort).Varredura Iteração Vetor de chave Salto Par comparado Ação

1 1 28 26 30 24 25 3 28,24 troca2 24 26 30 28 25 3 26,25 troca

2 3 24 25 30 28 26 2 24,30 não troca4 24 25 30 28 26 2 25,28 não troca5 24 25 30 28 26 2 30,26 troca

3 6 24 25 26 28 30 1 24,25 não troca7 24 25 26 28 30 1 25,26 não troca8 24 25 26 28 30 1 26,28 não troca9 24 25 26 28 30 1 28,30 não troca

6.3.2 Implementaçãoint calcula_salto (int nsalto){nsalto = nsalto / 1.3;if ( (nsalto == 9) || (nsalto == 10) ) nsalto=11;return (nsalto);}

void comb_sort (void){int i, aux, salto,troca;salto = MAX;do

{salto = calcula_salto(salto);for ( i = 0 ; i < (MAX-salto) ; i++ )

{if ( (i+salto) < MAX )

{if ( vetor[i] > vetor[i+salto] )

{aux = vetor[i];vetor[i] = vetor[i+salto];vetor[i+salto] = aux ;}

}else

break;}

} while ( salto >= 1 );}

Observe que quando h=1, o método se confunde com o bubblesort.

6.4 Método de Partição e Troca - QuicksortO método apresentado a seguir foi proposto por Hoare. Seu desempenho é tão

espetacular, que seu inventor denominou-o “quicksort”, ou seja, “ordenação rápida”. De fato,comparado com os demais métodos, é o que apresenta, em média, o menor tempo declassificação. Isto porque, embora tenha um desempenho logarítmico como muitos outros, é oque apresenta menor número de operações elementares por iteração. Isto significa que,mesmo que tenha que efetuar uma quantidade de iterações proporcional a n log2 n, cada umadelas será mais rápida.

43

6.4.1 Descrição do Método

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 n

vetor particionado:1 k-1 k k+1 n

S1 S2 S3

Observe que, pelo fato de C[i] <= C[k] para i=1,...,k-1, e C[i] > C[k] para i = k+1,...,n, achave particionadora C[kl ocupa a sua posição definitiva correta na ordenação.

O processo de particionamento é reaplicado aos segmentos S1 e S3 e a todos ossegmentos correspondentes daí resultantes, que tiverem comprimento >=1. Quando nãorestarem segmentos a serem particionados, o vetor estará ordenado.

Como vemos, o método consiste na aplicação sucessiva da operação departicionamento de segmentos, que é a operação básica do método.

Assim sendo, esta operação deve ser implementada de forma simples e eficiente. Umdos pontos principais da operação é o da escolha da chave particionadora, já que o seu valordeterminará o tamanho dos segmentos S1 e S3. A chave particionadora ideal é aquela queproduz segmentos S1 e de igual tamanho (ou aproximado). Isto pode ser obtido se o seu valorfor igual ao da chave de valor mediano. Entretanto, para encontrarmos tal chave, serianecessário percorrer todo o vetor a ser particionado. Este procedimento tornaria a operaçãolenta, pois deve ser aplicado a todos os segmentos de comprimento maior ou igual a um e quese formam após cada particionamento.

Para evitar esse problema, devemos usar um critério de escolha simples e rápido, depreferência que não envolva uma pesquisa entre as chaves. Ora, se não tivermos nenhumconhecimento prévio sobre a distribuição dos valores das chaves, podemos supor que, emprincípio, qualquer uma delas pode ser a particionadora. Tendo isto em vista, e com afinalidade de simplificar o algoritmo de particionamento, arbitraremos que a chave que seencontra na posição inicial do vetor a ser particionado será a particionadora.

Caso, no entanto, tenhamos um conhecimento prévio sobre a distribuição dos valoresdas chaves, podemos usar um outro critério de escolha. Por exemplo, se soubermos que ovetor já se encontra parcialmente ordenado, podemos eleger como particionadora aquelachave que se encontra na posição central do vetor.

O exemplo a seguir ilustra o processo de particionamento, usando a chave inicial dovetor como particionadora.

O algoritmo executa o particionamento em n passos (n = número de chaves). Nos n-1primeiros, 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

44

chave particionadora é inserida na sua posição definitiva correta.Suponhamos o vetor abaixo:

9 25 10 18 5 7 15 3Escolhemos a chave 9 como particionadora e a guardamos em uma variável

temporária (cp). Com isto, a posição ocupada por ela se torna disponível para ser ocupada poroutra chave. Esta situação é indicada pelo símbolo x :

� 25 10 18 5 7 15 3 cp=9

Marcamos também o início e o fim do vetor por dois apontadores: i (de início) e f (defim). A expressão “esquerda” escrita ao lado do vetor indica que a posição apontada peloponteiro i (o da esquerda) está disponível e pode ser ocupada por outra chave. Nos passosseguintes, a expressão “direita” indica o contrário.

i f↓ ↓

1. � 25 10 18 5 7 15 3 esquerdaA 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 ondeficam as chaves menores ou iguais à particionadora), ao mesmo tempo em que avançamos oponteiro i para indicar que a chave recém-movida já se encontra no segmento correto. A novaposição vaga passa a ser a apontada por f:

i f↓ ↓

2. 3 25 10 18 5 7 15 � direitaAgora comparamos a chave 25 (pois a nova posição vaga é a da direita) com a

particionadora. Como aquela é maior, a deslocamos para a posição vaga, ao mesmo tempo emque recuamos o ponteiro fuma posição para a esquerda, indicando assim que a chave 25 já seencontra no seu segmento correto. Agora a posição vaga é a da esquerda:

i f↓ ↓

3. 3 � 10 18 5 7 15 25 esquerdaO 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 daesquerda:

i f↓ ↓

4. 3 � 10 18 5 7 15 25 esquerdaNo passo seguinte a chave 7 é colocada na posição vaga, e o ponteiro i é ajustado:

i f↓ ↓

5. 3 7 10 18 5 � 15 25 direitaOs passos seguintes são feitos de forma similar e são mostrados a seguir:

i f↓ ↓

6. 3 7 � 18 5 10 15 25 esquerda

45

i f↓ ↓

7. 3 7 5 18 � 10 15 25 direitaO resultado do 7º passo (correspondente ao n-1) produz a situação abaixo, na qual os

dois ponteiros i e j se encontram. Quando isto ocorre, os segmentos S1 e S3 já estãoformados. A posição vaga que fica entre eles corresponde à posição do segmento S2, ou seja,aquele que contém a chave particionadora.

i,f↓

3 7 5 � 18 10 15 25Assim, resta copiar o valor da chave particionadora na posição apontada por i e j, que o

processo de particionamento estará completado:

8. 3 7 5 9 18 10 15 25Observe que, embora os segmentos Si e S3 não estejam ainda ordenados, a chave

particionadora já se encontra na sua posição definitiva correta.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 seformando.

A seqüência a seguir exibe apenas o estado final de cada processo departicionamento. As chaves particionadoras são mostradas em tipo negrito, enquanto ossegmentos de apenas um elemento que se formarem são mostrados em tipo itálico.

3 7 5 9 15 10 18 253 5 7 9 10 15 18 25

O que encerra a ordenação do vetor.


A implementação do método exigirá, portanto, a definição de dois procedimentos: umpara executar os particionamentos, e outro para efetuar todos os particionamentos necessários.O primeiro procedimento, denominado partição é a seguir apresentado.

int particao (int inicio, int fim){int esquerda=1, cp = vetor[inicio];while (inicio < fim)

{if (esquerda)

{if (cp >= vetor[fim]) // troca para S1 (esquerda)

{vetor[inicio] = vetor[fim];vetor[fim] = 0;inicio++;esquerda = 0 ;}

elsefim--;

}else

{

46

if (cp < vetor [inicio]) // troca para S3 (direita){vetor[fim] = vetor[inicio];vetor[inicio] = 0;fim--;esquerda = 1;}

elseinicio++;

}}

vetor[inicio] = cp;return(inicio);} // fim funcao particao

Uma alternativa de implementação da operação de particionamento, adequada quandoa chave particionadora escolhida ocupar uma posição intermediária do vetor a ser particionadoe possuir um valor mediano, foi proposta por N. Wirth, e funciona da seguinte forma: uma vezescolhida a chave particionadora (denominada cp), percorre-se o vetor a ser particionado daesquerda para a direita, até que seja encontrada uma chave c[i] > cp. A seguir percorre-se ovetor da direita para a esquerda, até que seja encontrada uma chave c[j] <= cp. Nesta ocasiãoas duas chaves c[i] e c[j] são permutadas de posição. As varreduras prosseguem a partirdestes pontos, até que os dois deslocamentos se encontrem em uma posição intermediária dosegmento. A esquerda ficarão as chaves menores ou iguais à particionadora. A direita asmaiores. 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.

Independentemente da implementação usada para efetuar os particionamentos,devemos implementar o procedimento que irá efetuar todos os particionamentos necessáriospara ordenar o vetor. Essa operação (particionamento sucessivo) é claramente recursiva, umavez que, obtido o primeiro particionamento, a operação é reaplicada sobre os segmentosresultantes, até que todas as partições fiquem reduzidas a um único elemento. Assim, oprocedimento que implementa a operação refletirá esta natureza recursiva, sendo recursivotambém:

void quick_sort (int comeco, int final){int divisor;if ( final > comeco )

{divisor = particao (comeco, final); // particionaquick_sort(comeco, divisor-1); // ordena segmento a direitaquick_sort(divisor+1,final); // ordena segmento a esquerda}

} // fim funcao quick_sort

Em linguagens de programação que não suportam a recursividade, a implementaçãodo procedimento quicksort deve manipular explicitamente a pilha de pedidos pendentes departicionamento. Deixaremos a implementação dessa alternativa como exercício.


A análise que será feita a seguir é baseada na implementação da operação departicionamento descrita inicialmente.

Esta implementação, ao contrário da segunda alternativa proposta, não efetua trocas(que implicam uma operação triangular). Para cada chave encontrada fora do seu segmento, éfeita apenas uma transposição da mesma para a posição vaga existente. Essa operação

47

(transposição de segmento) não será considerada na análise. Apenas consideraremos aquantidade de comparações efetuadas para decidir em que segmento deve se localizar cadauma das chaves.

Como comparamos a chave particionadora com todas as demais, obviamente sempreserão requeridas n-1 comparações para particionar n chaves.

Supondo, agora, a situação ideal em que a chave particionadora seja tal que oparticionamento produza dois segmentos S1 e S3 de igual tamanho, teremos dividido o vetorde 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 queserã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

48

(n-1)/2 (n-1)/21

(n-1)/2 (n-1)/2

(n-3)/4 (n-3)/4

(n-7)/8 (n-7)/8 (n-7)/8 (n-7)/8

(n-3)/4 (n-3)/4

(n-7)/8 (n-7)/8 (n-7)/8 (n-7)/8

1

1 1

1 1 1 1

condição deixará de ocorrer após executados log2 n passos de particionamento (a= maiorinteiro <= a).

Logo, o total das comparações a serem efetuadas é igual à soma do número decomparações efetuadas em cada passo, ou seja:

Este seria, pois, o melhor caso para o método. Naturalmente, não devemos esperarque isto ocorra em situações normais. Supondo que as chaves sejam únicas, a probabilidadede escolhermos ao acaso exatamente a particionadora mediana é 1/n. No entanto, segundoWirth, quando escolhemos a chave particionadora aleatoriamente, o desempenho médio doquicksort se torna inferior ao do caso ótimo de um fator da ordem de apenas 2 ln 2.

Há, ainda, a considerar o pior caso. Este se configura quando a chave particionadoraescolhida é a menor (ou a maior) de todas. Nesse caso, e persistindo a situação em todos osdemais particionamentos, o método se torna extremamente lento, com desempenhoquadrático. De fato, se a chave escolhida for sempre a menor de todas, os particionamentosproduzirão os segmentos S1 vazios e os S3 com n-1 elementos, conforme o esquemamostrado adiante.

Sendo necessários, pois, n-1 passos, cada um deles exigindo um número decomparaçõ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)/2Esse 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.

49

7 Classificação por SeleçãoOs 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 suaposição definitiva correta, qual seja, no início (ou no final) do vetor, por permutação com a queocupa 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érioutilizado para selecionar, a cada iteração, a chave de menor (ou maior) valor.

7.1 Método de Seleção DiretaNeste 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, quefica, assim, reduzido de um elemento. O processo de seleção é repetido para a parte restantedo vetor, sucessivamente, até que todas as chaves tenham sido selecionadas e colocadas emsuas posições definitivas.

7.1.1 Exemplo

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á 7iterações, conforme mostrado na tabela a seguir.

Tabela 7.1 Demonstração do Método de Seleção DiretaIteração

Vetor Chave Permutação Vetor ordenado atéa posição

1 9 25 10 18 5 7 15 3 3 9 – 32 3 25 10 18 5 7 15 9 5 25 – 5 13 3 5 10 18 25 7 15 9 7 10 – 7 24 3 5 7 18 25 10 15 9 9 18 – 9 25 3 5 7 9 25 10 15 18 10 10 – 25 46 3 5 7 9 10 25 15 18 15 15 – 25 57 3 5 7 9 10 15 25 18 18 25 – 18 6

3 5 7 9 10 15 18 25 8

Observe que a última iteração (7ª) encerra a classificação, pois se as n-1 menoreschaves do vetor estão em suas posições definitivas corretas, então a maior (e última)automaticamente também estará.


A implementação do método é direta. O procedimento a seguir toma a primeira chaveda 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 valorinferior, passa a considerar esta como a menor. Ao final de cada iteração, a menor chaveencontrada é inserida na primeira posição da parte não classificada, que assim fica reduzida deum elemento.

50

void selecao_direta (void){int i, j, ind_x, menor;

for (i=0; i<MAX-1; i++){menor = vetor[i];ind_x = i;

for (j=i+1; j<MAX; j++){if (vetor[j] < menor)

{menor = vetor[j];ind_x = j;}

}vetor[ind_x] = vetor[i];vetor[i] = menor;}

} // fim selecao_direta

7.1.3Análise do Desempenho

Na análise do desempenho do método de seleção direta podemos considerar doisaspectos: a quantidade de comparações efetuadas e a quantidade de trocas de mínimosefetuadas.

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, neste método, 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 fazercom que os tempos de classificação de dois vetores com as mesmas chaves, porém arranjadasde formas diversas, possam ser diferentes.

Supondo que a distribuição dos valores das chaves seja uniforme, então o númeromédio de trocas de mínimos efetuadas ao longo de uma iteração pode ser estimado daseguinte forma: a probabilidade de que a segunda chave seja menor do que a primeira (tomadacomo mínimo inicial) é 1/2. A probabilidade de que a terceira chave seja menor do que as duasprimeiras é 1/3. A probabilidade da quarta ser menor do que as três primeiras é 1/4 e, assimpor diante, até a última chave, cuja probabilidade de ser menor do que todas as n-1 que aantecedem é 1/n. Estes valores correspondem às freqüências relativas com que cada troca vaiocorrer. 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 comosé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:

51

O símbolo y representa a constante de Euler, cujo valor é 0,5772157...

7.2 Método da Seleção em Árvore - HeapsortA 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 é amenor dentre n chaves. Por outro lado, essa condição só é absolutamente necessária naprimeira varredura. Ao final desta, podemos reter outras informações além da identificação damenor 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. Nasegunda varredura será necessário operar apenas com o segmento que forneceu a menorchave, ou seja, trabalharemos com n/2 chaves ao invés de n-1, o que já representa um ganhosignificativo. Uma vez encontrada a segunda menor chave deste segmento, a comparamoscom 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 tantossegmentos quantos forem possíveis, de tal forma a minimizar a quantidade de comparações aser 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 dechaves sucessivamente dividido ao meio, sendo a menor chave de cada segmento identificadaem negrito.

Tabela 7.2: Exemplo de aplicação Método Heapsort.15 09 18 25 14 10 22 1215 09 18 25 14 10 22 1215 09 18 25 14 10 22 1215 09 18 25 14 10 22 12

A identificação da menor chave em cada um dos sucessivos segmentos nos quais ovetor foi subdividido pode ser representada pela seguinte estrutura de árvore:

52

Figura 7.1 Árvore das menores chaves de cada segmento.

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, pelaschaves sucessoras (na ordem crescente), de cada subárvore, permanecendo livre apenas aúltima posição anteriormente ocupada pela chave removida. Na Figura 7.2a vemos a árvorecom a chave 09 removida e, na Figura 7.2b, vemos as vagas por ela deixadas ocupadas pelaschaves sucessoras.

Figura 7.2a Remoção da menor chave.

Figura 7.2b Promoção da sucessora.

53

09

09 10

09 18 10 12

15 1014 2225 121809

O

O 10

O 18 10 12

15 1014 2225 1218O

10

15 10

15 18 10 12

15 1014 2225 1218O

Desse modo, a segunda menor chave aparecerá na raiz da árvore e poderá serremovida, seguindo-se a promoção da terceira menor chave, mostrada na Figura 7.3. Esseprocesso se repete até que todas as n chaves tenham sido removidas.

Figura 7.3 Promoção da terceira menor chave.

Observe que, a cada nível da árvore que se desce, o problema fica reduzido pelametade, pois apenas uma subárvore é afetada pela remoção da chave. Com isso, a cadaiteração, evitamos trabalhar com a totalidade das chaves restantes, o que irá acelerar bastantea seleção da menor chave em cada iteração. Este é, pois, o princípio básico do método deseleção em árvore.


A implementação, proposta por J. Williams, permite simplificar ainda mais a estruturade árvore que mantém a hierarquia das chaves. A simplificação elimina a redundância deocorrências de chaves na árvore, fazendo com que ela possua exatamente n nodos, ao invésdos 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 arepresentaçã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 direitade Ci para i=1, n div 2.

Exemplificando: dado o vetor C1..7, e utilizando a interpretação anterior, podemos vê-locomo sendo a representação da árvore mostrada na Figura 7.4.

Figura 7.4 Árvore representada pelo vetor C1..7.

54

12

15 12

15 18 14 12

15 O14 2225 1218O

C2

C3

C4

C5

C6

C7

C1

O passo seguinte consiste em trocar as chaves de posição dentro do vetor, de tal formaque estas passem a formar uma hierarquia, na qual todas as raízes das subárvores sejammaiores ou iguais a qualquer uma das suas sucessoras, ou seja, cada raiz deve satisfazer asseguintes condições:

Ci >= C2i e Ci >= C2i+1para 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, podemosafirmar 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 talforma que a árvore representada passe a ser um heap. Esse processo pode ser feito testando-se cada uma das subárvores para verificar se elas satisfazem, separadamente, a condição deheap. Naturalmente, apenas as subárvores que possuem pelo menos um sucessor devem sertestadas. 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-se, a partirdaí, para as subárvores que antecedem esta, até testar a raiz da árvore.

Desse modo, a primeira subárvore da Figura 7.4a 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 componentesdevem ser rearranjados de modo a formar o heap. Por exemplo, se for encontrada umasubárvore como a da Figura 7.5 (a), seus componentes devem ser rearranjados na forma daFigura 7.5 (b).

Figura 7.5 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. Essapossibilidade obriga a verificar, sempre que for rearranjada uma subárvore, se a sucessora doní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 712 09 13 25 18 10 22

Cuja interpretação sob a forma de árvore é:

55

10 12

5 12 5 10

a)b)

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 aconfiguração da árvore e do vetor correspondente mostrada na Figura 8.6.

Figura 7.6: 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 7.7.


E finalmente a de raiz 12, na figura abaixo.

56

09 13

25 18 10 22

12


Nesse caso ocorreu aquela possibilidade anteriormente mencionada, naqual a transformação de uma subárvore poderia afetar outra de um nível abaixo.A subárvore afetada deve ser rearranjada, conforme mostra a figura abaixo.

Figura 7.9: 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 daschaves seguintes será bastante simplificada.

Se a chave que está na raiz é a maior de todas, então sua posição definitiva correta naordem crescente é na última posição do vetor, onde ela é colocada, por troca com a chave queocupa aquela posição. Com a maior chave já ocupando a sua posição definitiva podemos, apartir de agora, considerar o vetor como tendo um elemento a menos, o qual será mostrado novetor (área sombreada), mas não aparecerá na árvore correspondente, conforme ilustrado nafigura a seguir.

57

Figura 7.10: 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 estasubá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 imediatamenteabaixo.

Figura 7.11: Seleção da segunda maior chave.

Novamente a maior chave dentre as restantes aparece na raiz (perceba a pequenaquantidade de comparações necessárias para efetuar a seleção desta chave). A Figura 7.12mostra a segunda maior chave sendo colocada em sua posição definitiva correta, de formaidêntica ao do caso anterior.

Figura 7.12: Colocação da segunda maior chave em sua posição.

58

Na figura seguir a árvore é novamente rearranjada para formar um heap, o quepermitirá selecionar a próxima chave.

Figura 7.13: Seleção da terceira maior chave.

Os demais passos seguem o mesmo princípio e são mostrados na figura, a seguir.Observe que, da mesma forma que no caso da seleção direta, a classificação estará encerradaapós a iteração n-1, pois teremos selecionado as n-1 maiores chaves, restando, assim, apenasa menor de todas, que automaticamente estará ocupando a posição inicial do vetor, o queencerra a classificação.

Figura 7.14: Final do processo de classificação.

O algoritmo que implementa esse método segue exatamente a descrição anterior. Para

59

simplificar a manipulação do vetor, foi criada uma função auxiliar keyval, que retorna o valor dachave 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. Porexemplo, 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, assegurandoo término natural do processamento.

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 59 */

int keyval (c, n, i){if (i > n )

keyval(minkey)else

keyval(c[i]);}

Com auxílio de keyval, escrevemos o procedimento heap, cuja finalidade é transformarem 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 foiafetada. Em caso afirmativo, a verificação também se estende a ela. O processo se encerraquando não houver mais trocas, ou quando for atingido o nível das folhas da árvore.

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 60 */void heap (c, n, r){i = r; troca = 1;while (troca)

{ // procura maior subárvoreif ( keyval(c, n, 2*i) > keyval(c, n, 2*i+1) )

h = 2*i; // subárvore da esquerdaelse

h = 2*i+1; // subárvore da direitaif ( c[i] < keyval(c, n, h) ) // compara raiz com o maior sucessor

{aux = c[i]; // trocac[i] = c[h];c[h] = aux;i = h ; // desce p/raiz da subárvore afetada pela troca}

elsetroca = 0; // se não houve troca

}}

Resta agora escrever o procedimento final, que denominaremos heapsort. Este seráconstituído de duas partes. A primeira fará a formação do heap inicial, ou seja, preparará aárvore para a seleção da maior chave. A segunda parte, que denominaremos manutenção doheap, rearranjará a árvore após cada seleção da maior chave, para que ela retome a forma deheap, permitindo assim a seleção da próxima chave. Essa segunda parte demanda n-1iterações, e corresponde à fase de classificação propriamente dita.

60

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 61 */void heapsort(c, n){i = n div 2; // raiz da última árvorefor (r = i; r > 1 ; r--) // formação do heap inicial

heap (c, n, r);for ( n1= n-1 ; n>1 ; n1—) // manutenção do heap

{ // coloca a maior chave em sua posiçãoaux = c[1];c[1] = c[n1+1];c[n1+1] = aux ;heap (c, n1, 1); // refaz heap a partir da raiz da árvore}

}


Na análise do desempenho do heapsort, devemos considerar separadamente as duasfases 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 aschaves já satisfazem as condições Ci >= C2i e Ci >= C2i+1, para i=1, n div 2. Uma permutaçãoque satisfaz essas condições é a do vetor na ordem decrescente, ou seja, na ordem contrária àdesejada. Nesses casos, a árvore derivada já forma um heap, não sendo necessária nenhumatroca de posição entre as chaves. Apenas serão efetuadas 2 x (n div 2) comparações (duaspara cada subárvore testada), para se certificar de que a árvore é um heap.

Com vistas à simplificação da análise, consideraremos a divisão exata n/2 ao invés dadivisão inteira n div 2. Isto afeta em meia unidade apenas os casos de n ímpar. Assim, onúmero de comparações no melhor caso será considerado como sendo igual a n e não a 2 (ndiv 2).

Ao contrário, o pior caso para a formação do heap é aquele no qual o vetor já seencontra na ordem desejada. Nesta situação, além de haver trocas em cada uma das n/2subárvores examinadas, as trocas sempre afetarão as demais subárvores dos níveis inferiores,até o último nível, pois as chaves rebaixadas em cada subárvore serão sempre as menores, asquais deverão se localizar nas folhas. Assim, teremos as n comparações seguidas de n/2trocas, acrescidas daquelas comparações e trocas referentes ao escorregamento das chavesmenores até o nível das folhas.

Para calcularmos esta quantidade extra de comparações e trocas, podemos usar atécnica da indução, calculando quantas serão efetuadas a partir de cada nível da árvore,iniciando pela raiz (nível 1), obtendo, a seguir, a expressão que generaliza para qualquer nível.

No caso da subárvore da raiz, teremos uma troca para que ela, isoladamente, formeum heap, seguida de log2 (n)-2 trocas correspondentes ao escorregamento da chave rebaixadaaté o nível das folhas. No nível 2, além das duas trocas correspondentes às duas subárvoresdeste nível, teremos 2x(log2(n)-3) trocas devidas ao escorregamento até o nível das folhas, eassim sucessivamente até o penúltimo nível, no qual somente haverá trocas referentes àtransformação das subárvores em heaps, já que, por formar o último nível de subárvores, nãohá propagação.

7.3 Método de Seleção em Árvore Amarrada - ThreadedheapsortA fase de manutenção do heap pode ser implementada de forma alternativa. Ao invés

de trocar o elemento da raiz com aquele que ocupa a última posição do vetor, provocando anecessidade de rearranjar o heap, podemos colocá-lo em um vetor auxiliar, em sua posiçãocorreta e, depois, simplesmente promover as chaves sucessoras de cada subárvore a partir da

61

raiz.Tudo se passa como se as chaves sucessoras de cada raiz de subárvore estivessem

“amarradas” umas às outras e, ao removermos a raiz da árvore, a sua sucessora seria puxadapela amarra, ocupando assim o lugar vago da raiz, trazendo, ao mesmo tempo, um nível acima,as demais sucessoras ligadas pelas amarras. A última chave dessa cadeia deixaria um vaziono seu lugar. Quando da implementação, esse vazio pode ser representado por um valorsingular de chave, tal como minkey, já utilizado na função keyval.

A seqüência de quadros da figura 7.15a e 7.15b ilustram esse processo, partindo doheap já formado. O valor minkey está representado pelo símbolo (*). Os arcos representam asamarras. A seta apontando para cima sobre a raiz indica que esta será removida. Abaixo decada árvore é mostrado o vetor de chaves (acima) e o vetor auxiliar (abaixo).

Figura 7.15a: Manutenção do heap por arrasto das chaves sucessoras (1a parte).

Figura 7.15b: Manutenção do heap das chaves sucessoras (2a parte).

O algoritmo que implementa esta alternativa é bastante semelhante ao já apresentado,

62

e é praticamente auto-explicativo. O procedimento pull up faz o papel das amarras,promovendo a ascensão de cada uma das chaves sucessoras um nível acima do qual seencontram. Já o procedimento threadedheapsort trata de construir o heap inicial (de formaidêntica ao heapsort) e, na fase de manutenção, a cada iteração, coloca o elemento da raiz nasua posição correta no vetor auxiliar c’ a executa a operação pull up.

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 72 */

void pull_up (c, n){i = 1;do

{if ( keyval(c,n,2*i) > keyval(c, n, 2*i+1)

h = 2*i; // amarra sucessor da esquerdaelse

h = 2*i+1; // amarra sucessor da direitachave = keyval(c, n, h); // obtem valor do sucessorc[i] = chave ; // promove um nível i = h; // desce} while ( chave = minkey);

}

void threadedheapsort (c, c', n){i = n div 2;for ( k = i; k > 1 ; k --) // formação do heap

heap (c, n, k);c'[n] = c[1];for (k = n-1 ; k > 1 ; k --) // manutenção do heap

{pull_up(c, n); // promove chaves sucessorasc'[k] = c[1]; // coloca a maior chave em sua posição}

}

A análise da fase de manutenção neste caso é mais simples, uma vez que todas aschaves, com exceção daquela que já se encontra na raiz, deverão subir desde o nível ondeestão até o nível 1. Dessa forma, teremos 2 chaves subindo 1 nível, 4 chaves subindo 2, 8subindo 3 e assim por diante.

Esse valor corresponde à quantidade total de níveis que as chaves subiram.Obviamente esse total é superior às trocas efetuadas pelo método heapsort em sua fase demanutenção, as quais correspondem a aproximadamente 3/4 do valor que obtivemos.

Entretanto, no caso do método threadedheapsort, não se trata de operações de trocas,mas simples transposições (atribuições) de chaves de um vetor para outro. Devemos então,para comparar as duas alternativas, computar as atribuições efetuadas em cada caso. Cadatroca do heapsort corresponde a três atribuições, enquanto cada operação de subida de níveldo threadedheapsort corresponde a somente uma atribuição. Assim, o total de atribuições doheapsort é expresso por (9/4)n * log2(n/4)+3n enquanto as atribuições do threadedheapsortcorrespondem a n x log2 (n/4)+n.

O que claramente corresponde a uma vantagem para esta alternativa. Além disso, aquantidade de comparações efetuadas também é menor, pois enquanto o heapsort efetua duascomparações para cada troca, o threadedheapsort efetua apenas uma para cada promoção denível. O Quadro 5.6 mostra as quantidades de operações efetuadas em cada um dos doismétodos na fase de manutenção do heap.

63

Tabela 7.3: Trocas para manter o heap.h Total de folhas Trocas de folhas Total de trocas1 1 0 1 * 0 = 02 2 1 2 * 1 = 23 4 2 4 * 2 = 84 8 3 8 * 3 = 245 16 4 16 * 4 = 64... ... ... ...m 2m-1 m-1 2m-1 * (m-1)

Tabela 7.4: Resumo das comparações e atribuições efetuadas.Manutenção do heap

Heapsort ThreadedheapsortAtribuições (9/4)n * log2(n/4)+3n n * log2(n/4)+n

Comparações (3/2)n * log2(n/4) n * log2(n/4)

A desvantagem do uso dessa alternativa é a necessidade de uma área extra pararepresentar o vetor ordenado.

64

8 Classificação por Distribuição de ChavesEste método de classificação antecede aos computadores digitais. Ele é uma

adaptação do processo de classificação mecânica de cartões perfurados, utilizados desde aprimeira metade do século XX como dispositivo para armazenamento de dados.

O modelo mais comum de cartão perfurado era aquele no qual podiam serrepresentados até 80 caracteres, dispostos em colunas, formando, cada um, um registro de umarquivo. Caracteres contíguos podiam representar um dado e recebiam a denominação decampo. Desta forma, o cartão era formado de um ou mais campos de dados, conforme aaplicação.

Antes do advento do computador, o cartão perfurado era usado em processosmecanizados, que envolviam basicamente as operações de tabulação, contagem e totalizaçãode dados. Como surgimento do computador digital, o cartão passou a ser usado também comomeio de entrada de dados. Em ambos os casos, freqüentemente surgia a necessidade deordenar fisicamente os cartões segundo os valores de um determinado campo de dados, paraque pudessem ser processados naquela ordem.

A operação de classificação dos cartões era feita por um equipamento que lia ainformação perfurada, em uma dada coluna de cada vez, e remetia o cartão para um escaninhocorrespondente ao valor lido.

Dessa forma, todos os cartões que possuíam o dígito “0” na coluna selecionada eramempilhados no escaninho 0. Os que possuíam o dígito “1”, no escaninho 1, e assim por diante.

Para obter os cartões ordenados pelo dígito da coluna selecionada, bastava recolhê-losdos escaninhos na ordem crescente, ou seja, primeiro os do escaninho 0, depois os doescaninho 1 e assim até o 9.

Quando o dado a ser classificado ocupava um campo com mais de uma coluna(possuía mais de um dígito), era necessário efetuar tantos passos de ordenações quantosfossem os dígitos, iniciando-se pelo de menor ordem (o das unidades), prosseguindo-se daí emdiante até o de mais alta ordem. Após classificar cada coluna, as pilhas formadas em cadaescaninho eram colocadas umas sobre as outras, na ordem crescente, sendo repetido oprocesso para as colunas seguintes, sucessivamente, até a última.

Por exemplo, suponhamos que um arquivo formado por 20 cartões tivesse, em umcerto campo, os seguintes valores perfurados:

523, 018, 125, 937, 628, 431, 243, 705, 891, 362, 429, 005, 540, 353, 115, 427, 910,580, 174, 456

A classificação pela coluna que contém o dígito da unidade produziria a seguintedistribuição pelos escaninhos:

115580 353 005910 891 243 705 427 628540 431 362 523 174 125 456 937 018 4260 1 2 3 4 5 6 7 8 9

Recolhendo os cartões na ordem descrita, obteremos:540, 910, 580, 431, 891, 362, 523, 243, 353, 174, 125, 705, 005, 115, 456, 937, 427,

018, 628, 429Classificando agora pela coluna das dezenas obtemos :

65

429628

018 427005 115 125 937 243 456705 910 523 431 540 353 362 174 580 8910 1 2 3 4 5 6 7 8 9

Recolhendo-os em ordem:705, 005, 910, 115, 018, 523, 125, 427, 628, 429, 431, 937, 540, 243, 353, 456, 362,

174, 580, 891E finalmente classificando pela coluna da centena e depois retirando-os em ordem,

obtemos os cartões na ordem desejada:

456174 431 580

018 125 362 429 540 937005 115 243 352 427 523 628 705 891 9100 1 2 3 4 5 6 7 8 9

005, 018, 115, 125, 174, 243, 353, 362, 427, 429, 431, 456, 523,540,580,628, 705,891,910,937

O mesmo processo podia ser aplicado em campos com dados alfanuméricos, exigindono entanto que cada passo fosse desdobrado em duas etapas, já que os caracteres alfabéticoseram representados por meio de duplas perfurações em cada coluna do cartão.

8.1 Método de Indexação Direta - RadixsortA utilização deste princípio para classificar dados usando um computador é

aparentemente desvantajosa, pois o processo requer tantos passos de classificação quantossão os dígitos dos dados. Entretanto, como em cada passo somente um dígito do dado éconsiderado, podemos utilizá-lo como um índice que vai remeter o dado todo para o escaninhocorrespondente. Ou seja, não será necessário efetuar comparações entre os dados paraestabelecer a sua ordem relativa.

Resta-nos, assim, construir um mecanismo que simule de maneira eficiente osescaninhos da classificadora de cartões, considerando que não sabemos, a priori, qual acapacidade de empilhamento que deve ter cada um deles.

Para isto, temos duas alternativas. A primeira é construir uma lista encadeada onde osdados são inseridos à medida que são distribuídos segundo os valores de seus dígitos. Parasimplificar a administração da lista como um todo, pode-se manter uma lista (pilha) separadapara representar cada escaninho, juntamente com um vetor de cabeças que apontam para otopo de cada uma. O valor inicial dos ponteiros é null, indicando escaninhos vazios. Para quepossamos manter a informação que indica a base de cada pilha, podemos organizar as listassob forma circular, de modo que o nodo do topo aponte para o nodo da base. A manutenção

66

dessa informação é necessária para que possamos, ao final de cada passo, unir as listasformadas, e evita, ao mesmo tempo, a necessidade de manter outro vetor de ponteiros queapontem para as bases das pilhas.

À medida que os dados vão sendo distribuídos, os ponteiros correspondentes vãosendo atualizados, indicando o topo de cada pilha. Após a distribuição do último dado, as pilhasdevem ser concatenadas, formando a lista ordenada pelo dígito em questão. Deve haver umapontador cabeça para indicar o início da lista.

Dessa forma, a distribuição das chaves pelos escaninhos pode ser feita utilizando-se odígito selecionado para endereçar o vetor de ponteiros, inserindo-se a chave na posiçãoapontada pelo ponteiro correspondente, o que corresponde a distribuir a chave no topo do seuescaninho.

Visando minimizar as operações de alocação e desalocação dinâmica de nodos dalista, os mesmos podem ser reutilizados de um passo para outro, bastando efetuar o ajusteadequado dos ponteiros envolvidos, o que evita o uso de uma área extra de memória. Paratornar os passos homogêneos, é conveniente dispor inicialmente as chaves sob a forma delista encadeada.

A segunda alternativa para simular os escaninhos da máquina classificadora écontabilizar previamente a quantidade de dados que conterá cada um deles. Com estainformação, podemos utilizar uma estrutura de vetor (não encadeado) para representar osescaninhos, já que a posição inicial de cada um deles pode ser calculada.

Os ponteiros foram obtidos calculando-se as freqüências acumuladas dos dígitos, eapontam para a primeira posição livre (topo) de cada escaninho. À medida que as chaves vãosendo distribuídas pelos escaninhos, os ponteiros vão sendo incrementados, passando aindicar as próximas posições livres.

Para executar o primeiro passo do exemplo, obtemos as seguintes freqüências deocorrência de cada dígito, as quais nos permitem calcular as freqüências acumuladas, que porsua vez indicam a posição inicial de cada escaninho:

Tabela 8.1: Freqüências acumuladas por escaninho. Dígito 0 1 2 3 4 5 6 7 8 9freqüência 3 2 1 3 1 4 1 2 2 1freq. acumulada 0 3 5 6 9 10 14 15 17 19

Esta segunda alternativa possui a vantagem de dispensar o uso de ponteiros. Por outrolado, exige uma varredura prévia das chaves para contabilizar as freqüências de ocorrênciados dígitos.

Independentemente da alternativa de implementação utilizada, o método possui avantagem de podermos adaptar a máquina classificadora para as chaves que vão serordenadas, caso estas possuam alguma característica especial que possa ser explorada paraobter alguma vantagem no processo como um todo.

Considere, por exemplo, a classificação de dados que representam os anos denascimento de um grupo de pessoas. Se considerarmos as chaves como um número comumde 4 dígitos cada, teremos de fazer a classificação em 4 passos. Entretanto, podemos observarque apenas no 1º e 2º passo podem ocorrer todos os dígitos de 0 a 9. No 3º passo os dígitospossíveis são 8, 9 e 0, enquanto que no 4º apenas o 1 e o 2 são possíveis.

De posse desta informação, podemos dividir as chaves de forma diferente. Agrupandoos dígitos da centena e do milhar, efetuaremos a classificação em três passos ao invés de

67

quatro, sendo o 1º e 2º normalmente processados, enquanto o 3º considerará os “dígitos” 18,19 e 20. Isto é possível, já que podemos construir a máquina classificadora com a quantidadede escaninhos que quisermos, cada um deles com o endereço que também quisermos. Nessecaso, para o terceiro passo teríamos apenas três escaninhos para receber as chaves quetiverem os valores 18, 19 e 20 na parte considerada. Certamente isto contribui para melhorar aeficiência do método.

Naturalmente, esse método não é recomendado para chaves muito longas, como porexemplo nomes de pessoas, pois além de exigir muitos passos para decidir a ordem, cadaparte da chave possui muitas alternativas (as letras do alfabeto, incluindo acentos, maiúsculase minúsculas). Nesses casos, recomenda-se o uso de métodos baseados em comparaçõesentre as chaves, pois muitas vezes apenas a 1ª letra do prenome é suficiente para decidir aordem relativa de dois nomes.

O procedimento distribuição, apresentado adiante, implementa a alternativa que usalistas encadeadas para representar os escaninhos, e efetua apenas um dos passos doprocesso de classificação, fazendo a distribuição da chaves segundo a iésima parte de cadauma delas. Supõe-se que os dados já se encontram sob a forma de uma lista encadeada, cujoprimeiro elemento é apontado pela variável início. Cada nodo da lista é um registro de doiscomponentes: a chave e o ponteiro para o nodo sucessor. Esses componentes são acessadospelas funções key (p) e next (p), respectivamente. O vetor top, de b elementos, indexados de 0a b-1, contém os ponteiros para os topos das pilhas que representam os escaninhos. A funçãoparte (i, k) extrai a parte i da chave k. A operação setnext (p, q) atribui o valor q ao componentenext do nodo apontado por p. A execução do procedimento redistribui os nodos da lista demodo que estes se apresentem ordenados segundo a parte i das chaves. A variável inícioaponta para o início da nova lista.

A operação de inserção de um nodo em um escaninho vazio está esquematizada naFigura 8.1, e a de um nodo em um escaninho não vazio na Figura 8.2.

Figura 8.1: Inserção de um nodo em um escaninho vazio.

Figura 8.2: Inserção de um nodo em um escaninho não vazio.

68

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 82 */void distribuicao ( inicio, i, b){// inicializacaop = inicio ;if ( p != null )

{for ( j = 0 ; j < b-1 ; j++)

top [j] = null;while ( p != null) // distribuicao das chaves

{d = parte ( i, key(p) ); // extrai parte i da chaveinicio = next(p);if top[d] = null

setnext( p, p );else

{ // escaninho 'd' não vazio setnext( p, next (top[d]) );setnext( top[d], p);}

top[d] = p; // topo do escaninho 'd'}

// concatena os escaninhosd = 0;while ( top[d] = null )

{d = d+1 ; // procura 1o escaninho vazio inicio = next( top[d] ); // inicio de nova lista ant = top[d]; // final provisório da lista j = d + 1 ; // proximo escaninho do

{if ( top[j] != null )

{ // concatena setnext( ant, next(top[j]) );ant = top[j];setnext(ant, null); // marca fim lista provisória}

j = j +1 ; // próximo escaninho} while ( j = b );

}}

A implementação da alternativa que utiliza um vetor no lugar da lista encadeada é maissimples, por não necessitar lidar com os ponteiros. Para este caso, será necessário, noentanto, utilizar um vetor de chaves auxiliar, uma vez que não podemos deslocar as posiçõesdos seus elementos como fizemos no caso da lista encadeada.

A implementação, que deixamos a cargo do aluno, está esquematizada a seguir:

func proc distribuicao;{inicialização;cálculo das freqüências;cálculo das freqüências acumuladas;distribuição das chaves}

Da mesma forma que na alternativa anterior, esse procedimento deverá ser repetidopara cada parte na qual as chaves foram divididas, atendo-se ao fato de que o resultado de umpasso de classificação sempre aparecerá no vetor auxiliar.

69

8.1.1 Desempenho

Este método apresenta a característica de possuir um desempenho determinístico, ouseja, sempre será executada a mesma quantidade de operações para uma dada quantidade nde chaves, independentemente da ordem com que estas se apresentam no início.

Como cada passo demanda exatamente n operações de distribuição, então aquantidade total de operações será n x np, sendo np o número de partes pelas quais as chavesestão divididas. Trata-se, pois, de um método de desempenho linear, ou seja, O (n).

Infelizmente, como já mencionado anteriormente, o método não é recomendado parachaves longas (np grande). Outra deficiência do método é que ele não pode ser aplicado, naforma como foi apresentado, em chaves numéricas que possuam valores negativos e positivosmisturados. Deixamos para o leitor a discussão deste caso e a proposta de soluções.

70

9 Classificação por IntercalaçãoA classificação por intercalação se baseia em um princípio de funcionamento bastante

simples. Consiste em dividir o vetor de chaves a ser classificado em dois ou mais, ordená-losseparadamente e, depois, intercalá-los dois a dois, formando, cada par intercalado, novossegmentos ordenados, os quais serão intercalados entre si, reiterando-se o processo até queresulte apenas um único segmento ordenado.

A Figura 9.1 ilustra esse processo, supondo uma divisão inicial em quatro segmentos.

Figura 9.1 Esquema do processo de intercalação.

Para obter a ordenação dos segmentos iniciais, pode ser usado qualquer método declassificação.

9.1 Método da Intercalação Simples - MergesortOutra alternativa é iniciar com segmentos de comprimento 1,os quais, por conterem

apenas um elemento cada, já estão ordenados. Dessa forma, consideramos, então, o vetor den elementos como sendo formado de n segmentos de 1 elemento cada, e aplicamos oprocesso reiterado de intercalação a partir daí, sem a necessidade de lançar mão de outrosmétodos de classificação para dar partida ao processo. Estudaremos essa alternativa. Aprimeira alternativa será discutida na seção intitulada Intercalação de Arquivos Classificados.

A Figura 9.2 mostra um exemplo deste princípio sendo aplicado a um vetor de 8chaves. Cada linha, a partir da segunda, corresponde ao resultado da intercalação de todos ospares de segmentos consecutivos da linha anterior.

23 17 8 15 9 12 19 717 23 8 15 9 12 7 198 15 17 23 7 9 12 197 8 9 12 15 17 19 23

Figura 9.2: Classificação por intercalação de um vetor de 8 chaves.

Quando o tamanho do vetor não for uma potência inteira de 2, sempre ocorrerá, empelo menos uma iteração, que um segmento resulte sem um par para ser intercalado. Quando

71

isto ocorrer, esse segmento, que obviamente sempre será o último do vetor, é simplesmentetranscrito para a iteração subseqüente, como no caso ilustrado na Figura 9.3.

23 17 8 15 9 12 19 7 14 1017 23 8 15 9 12 7 19 10 148 15 17 23 7 9 12 19 10 147 8 9 12 15 17 19 23 10 147 8 9 10 12 14 15 17 19 23

Figura 9.3 Intercalação com n <> 2i, i inteiro.


A implementação deste método será feita em três níveis. No primeiro, denominadosimplemerge, é definida a operação de intercalação de um par de segmentos ordenados,resultando um terceiro segmento também ordenado. O segundo nível, mergepass, fará aintercalação de todos os pares de segmentos ordenados nos quais o vetor está dividido. Oterceiro e último nível, mergesort, efetuará toda a seqüência de intercalações necessária paraque resulte apenas um segmento intercalado.

Esquematicamente, a implementação da operação simplemerge está representada naFigura 9.4. Os dois segmentos a serem intercalados ocupam posições contíguas no vetor C. Oprimeiro segmento inicia na posição isl e termina na fsl. O segundo ocupa as posições de is2até fs2. O resultado da intercalação aparece no vetor C’, a partir da posição r.

Figura 9.4 Esquema da operação simplemerge.

A operação mergepass, por sua vez, efetuará a intercalação de todos os paresconsecutivos de segmentos de comprimento L do vetor C.

Figura 9.5: Esquema da operação mergepass.

72

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 88 */void simplemerge (c, is1, fs1, is2, fs2, c', r){is1' = is1 ; is2' = is2; k = r;while ( (is1' <= fs1) an (is2' <= fs2) ) // enquanto não atingir o final de

{ // nenhum dos dois segmentos, compara if c[is1'] < c[is2'] // primeiros elementos de cada

segmento{c'[k] = c[is1']; // copia 1o elementois1' = is1' +1 ;}

else{c'[k] = c[is2']; // copia 2o elementois2' = is2' + 1;}

k = k + 1;}

if ( is1' > fs1 ) // verifica saldo dos segmentosfor ( i = is2' ; i < fs2 ; i ++) // copia resto do 2o segmento

{c' [k] = c[i] ;k = k + 1 ;}

elsefor ( i = is1' ; i < fs1 ; i ++ ) // copia resto do 1o segmento

{c' [k] = c[i] ;k = k + 1 ;}

}

void mergepass (c, c', n, L){ // L comprimento dos segmentosp = 1; // p = inicio do 1o segmentoq = p + L; // q = inicio do 2o segmentor = 1 ; // r = inicio do segmento resultantewhile ( q <= n) // enquanto houver pares de segmentos

{simplemerge(c, p, q-1, min(q+L-1,n), c', n) //intercala um par segmentosr = r + 2 * L; // proximo segmento resultantep = q + L; // proximo 1o segmentoq = p + L; // proximo 2o segmento}

if ( p <= n ) // verifica se último segmento possui par for ( i =p ; i < n ; i ++) // se não, transcreve para c'[p..n]

c'[i] = c[i]}

Observe que o 5º parâmetro de chamada da operação simplemerge, que indica aposição final do 2º segmento, prevê a possibilidade de que o último deles tenha umcomprimento menor do que L.

O nível final de implementação, visível ao usuário, deverá efetuar todas as seqüênciasde intercalações, desde as dos segmentos de comprimento 1, até obter um segmentointercalado de comprimento n, dobrando, após cada execução da operação mergepass, ocomprimento dos segmentos.

Devido ao fato da intercalação sempre ser feita em um vetor auxiliar, a operaçãomergepass deverá alternar sucessivamente os vetores de origem e destino. Dessa forma, asprimeiras intercalações serão feitas do vetor C para o C’. As segundas de C’ para C e assimaté o final. Ao concluir a última seqüência de intercalações, deve ser verificado em qual dosdois vetores, C ou C’, está o resultado final. Isto pode ser feito examinando-se a quantidade de

73

iterações executadas. Se estiver em C’, este é copiado para C, uma vez que C’ não é visível aousuário.

/* pseudo-código baseado em algoritmo de [Aze 96], Pg 89 */void mergesort ( c, n){L = 1 ;while ( L < n )

{if log2 L é par

mergepass(c, c', n, L); // c -> c'else

mergepass(c', c, n, L) // c' -> cL = 2 * L;}

if log2 n é impar // se última intercalação resultou c'for (i = 1 ; i < n ; i++)

c[i] = c'[i]}


Para fazermos a análise do desempenho deste método, é necessário primeiramenteestimarmos o número médio de comparações efetuadas para intercalar dois segmentos de nchaves cada um. Consideremos, por exemplo, o caso de dois segmentos de 4 chaves cada. Onúmero mínimo de comparações será 4 quando todos os elementos de um segmento foremmenores (ou maiores) do que os do outro. Assim, teremos dois casos que exigirão 4comparações. Por outro lado, o máximo será 7, quando o processo de intercalação tiver de seestender até o último elemento de cada segmento. Este exemplo nos permite verificar que aquantidade de comparações necessárias para intercalar dois segmentos de comprimento nvaria de n até 2n-1.

Ocorre que não podemos simplesmente considerar o número médio de comparaçõescomo sendo a média aritmética entre estes dois extremos (o que daria 5,5 para n=4), pois asfreqüências de cada caso não são as mesmas. No exemplo que estamos considerando, o casode 4 comparações ocorre apenas duas vezes, enquanto o de 7 comparações ocorre 40 vezes,conforme mostra a Tabela 9.1. Portanto, devemos considerar, isto sim, a média dasquantidades de comparações efetuadas, ponderadas pelas freqüências com que cada umadelas ocorre.

Tabela 9.1: Freqüência das comparações efetuadas para n = 4.Comparações (C) Freqüência (F) Freqüência ponderada (FxC)

4 2 85 8 406 20 1207 40 280

Total 70 448

Temos, pois, uma média ponderada de comparações igual a 448 / 70 = 6,4.Observando as freqüências das quantidades de comparações efetuadas, para diversos valoresde n, verificamos que estas se distribuem segundo o dobro das combinações (i-1/i-1), para i =n, 2n-1. As freqüências ocorrem no dobro deste valor porque, para cada par de segmento quecorresponde a uma permutação possível de ocorrer, existe o par reciproco, o qual exigirá amesma quantidade de comparações para ser intercalado.

Dessa forma, para qualquer valor de n, podemos tabular as freqüências, de acordocom a Tabela 9.2.

74

Tabela 9.2 Tabulação das freqüências.

O número esperado de comparações necessárias para intercalar dois segmentos de nelementos cada é dado, então, pela relação entre os dois totais da Tabela 7.2.

Para expressar essa relação sob a forma de uma função recorreremos à definição decombinações de ''r'' elementos tomados ''k'' de cada vez, e a três propriedades dascombinações.

75

10 Listas OrdenadasEsta seção apresenta uma estrutura de dados auto-ajustável, no sentido de sempre se

manter ordenada após cada inserção ou remoção. Devido a este comportamento altamentedinâmico, esta estrutura é perfeita para mostrar como a alocação dinâmica encadeada podeser utilizada na implementação de um tipo de dados abstrato.

Uma lista ordenada L:[a 1, a 2, ..., a n ] é uma lista linear tal que, sendo n > 1, temos:a) a 1 <= a k para qualquer 1 < k <= n;b) a k <= a n para qualquer 1 <= k < n;c) a k – 1 <= a k <= a k+1 , para qualquer 1 < k < n.

Se L é uma lista ordenada, podemos garantir que nenhum elemento em L é inferior a'a1' ou superior a 'an'. Além disso, tomando um elemento qualquer no meio da lista, nenhumelemento à sua esquerda o supera e nenhum elemento à sua direita é inferior a ele.

Entre as diversas operações que podem ser realizadas com uma lista ordenada,podemos destacar:� Ins (Inserir): insere um novo elemento na lista ordenada;� Rem (Remover): remove um elemento da lista ordenada;� Find (Encontrar): procura um elemento na lista ordenada.

Sendo L uma lista ordenada e 'x' um elemento qualquer, a operação Ins ( L, x )aumenta o tamanho da lista L , acrescentando o elemento 'x' na sua respectiva posição. Aoperação Rem ( L ) faz com que a lista diminua, se o elemento estiver na mesma, removendo oelemento e retornando verdadeiro. A operação Find ( L, x ) retornará a posição do elemento 'x'na lista.

Exercício 1: Dadas as operações sobre uma lista ordenada L, preencha o quadro aseguir com estado da lista e o resultado de cada operação:

Operação Estado da Lista Ordenada Resultado– L: [ ] –

Ins (L, 10) L: [ 10 ] –Ins (L, 15)Ins (L, 8)Ins (L, 12)Ins (L, 5)Ins (L, 20)Rem (L, 8)Rem (L, 10)Rem (L, 9)Find (L, 12)Ins (L, 13)

Find (L, 15)Find (L, 7)

Rem (L, 10)

10.1 Implementação Encadeada para Listas OrdenadasE óbvia a necessidade de inserir e remover elementos no meio de uma lista ordenada.

Para evitar o custo de movimentação de dados que teríamos numa implementação seqüencial,

76

utilizaremos alocação dinâmica encadeada ao implementar as listas ordenadas.Uma lista ordenada L:[a1, a2, a3, ..., an,] pode ser graficamente representada como

uma lista encadeada cujos nodos armazenam os elementos a1, a2, a3,.., an .

Figura 10.1: Lista ordenada na representação encadeada.

Como nenhum espaço de memória será alocado até que um elemento seja inserido nalista ordenada, para defini-la, precisamos apenas especificar o formato dos nodos e o tipo deponteiro que será usado para criar a variável L, que aponta o primeiro dos nodos encadeados:

/* define tipo 'elem' baseado em char */typedef char elem;

/* define tipo 'LstOrd' baseado em ponteiro para estrutura nodo */typedef struct nodo *LstOrd;

/* define estrutura nodo:- obj : caracter a ser armazenado- prox: ponteiro para proximo nodo */struct nodo

{elem obj;LstOrd prox;};

Obviamente, uma lista vazia é representada por um ponteiro cujo valor é nulo: [\] ou[NULL].

A inicialização e o teste de lista vazia são triviais nesta implementação, uma vezdefinido que um ponteiro com valor nulo representará uma lista vazia. Para criar uma listaordenada vazia, vamos usar a operação Criar () e para verificar se uma lista está vazia,usaremos a função Anular ():

int Criar (){L = NULL ;return(1);}

int Anular(){

if ( L == NULL )return(1);

elsereturn(0);

}

10.1.1 A Operação de Inserção

Ao inserir um elemento X numa lista L:[a1, a2, a3, ..., an], após ter sido alocado umnodo apontado por N para armazená-lo, temos quatro casos considerar:

a) A lista ordenada L está vazia.Neste caso, o nodo apontado por N passa a ser o primeiro da lista L. Para que isto

ocorra, devemos anular o campo de ligação do nodo apontado pois N, de modo a indicar quenenhum elemento além de X existe na lista. Em seguida, o endereço do nodo apontado por Ndeve ser copiado para a variável L, tal que ambos os ponteiros apontem o mesmo nodo.

77

N->prox = NULL ;L = N;

b) O elemento X é menor ou igual ao primeiro elemento da lista.O nodo N passa a ser o primeiro da lista, seguido imediatamente pelos nodos que já

estavam armazenados em L, isto é, indicamos que o nodo apontado por L passa a ser osucessor do nodo apontado por N e, finalmente, fazemos L apontar para o mesmo nodoapontado por N.

N->prox = L;L= N;

c) O elemento X é maior que o primeiro e existe outro que o supera.Neste caso, temos que encontrar na lista L o local correto para realizar a inserção.

Como não é possível o acesso direto aos nodos da lista encadeada, devemos partir do primeironodo e ir seguindo os campos de ligação, um a um, até encontrar o nodo que armazena umelemento ak, que supera X. Claramente, o nodo N deverá ser inserido antes de tal elemento.

P = L;while ( x > P->prox->obj )

P = p->prox;N->prox = P->prox;P->prox = N;

d) O elemento X é maior que todos os elementos de L.O nodo N será inserido no final da lista ordenada L. Novamente, partimos do primeiro

nodo e seguimos os campos de ligação até encontrar o último, após o qual o nodo N seráinserido.

P = L;while (P->prox != NULL)

P = P->prox;N->prox = NULL;P->prox = N;

78

Analisando os casos descritos acima, observamos uma grande semelhança entre osalgoritmos apresentados para os dois primeiros casos. Na verdade, eles são idênticos pois, noprimeiro algoritmo, podemos trocar NULL por L. Também os dois últimos casos podem serdescritos por um único algoritmo. Logo, o algoritmo completo para inserção pode ser codificadocomo a seguir:

int Inserir (elem x){LstOrd N, P;

N = (LstOrd *) malloc ( sizeof (LstOrd) ) ;

N->obj = x;

if ( ( Anular() ) || (x < L->obj) ) /* 1o e 2o casos */{N->prox = L;L = N;return(1);}

else{ /* 3o e 4o casos*/P = L;while ( (P->prox != NULL) && (x > P->prox->obj) )

P = P->prox;N->prox = P->prox;P->prox = N;return(1);}

}

10.1.2 A operação de Remoção

Diferentemente da inserção, que teoricamente sempre é possível, a remoção nemsempre pode ser realizada com sucesso. Por exemplo, qual seria o resultado da operaçãoRemover([a,b,c], d), se o elemento d não faz parte da lista?

Para sinalizar sucesso ou falha, a operação de remoção será implementada como umafunção lógica, que retorna verdadeiro ou falso de acordo com o sucesso ou não da operação.

Assim como na inserção, ao remover um elemento X de uma lista ordenada L,devemos considerar alguns casos importantes:

a) A lista ordenada L está vazia.Como o elemento X não pode estar contido numa lista vazia e, conseqüentemente, não

pode ser removido, a operação resulta em um valor lógico falso.

b) O elemento X é menor que o primeiro elemento da lista ordenada L.Como a lista L é ordenada, se X é menor que o primeiro elemento em L, então conclui-

se que X não está contido na lista e, portanto, não pode ser removido, e a operação resulta emfalso.

c) O elemento X é igual ao primeiro elemento da lista ordenada L.Neste caso, o primeiro nodo da cadeia deverá ser liberado e o ponteiro L atualizado de

modo a apontar o próximo nodo. Para poder acessar o nodo removido a fim de devolvê-lo aoespaço de memória livre, antes de desligá-lo da cadeia, precisamos fazer uma cópia do seuendereço.

79

d) O elemento X é maior que o primeiro elemento de L.Precisamos encontrar a posição ocupada por X. Partimos do primeiro nodo e, seguindo

os campos de ligação, vamos “caminhando” pela lista até encontrar um elemento ak cujo valoré maior ou igual a X. Se tivermos ak=X, então podemos removê-lo. Caso contrário, X não seencontra na lista e a operação falha. Também pode ocorrer de X ser maior que qualquer valorcontido na lista ordenada, e neste caso, constataremos a falha da operação quando atingirmoso último nodo da cadeia e ainda não tivermos encontrado o elemento X.

Os dois primeiros casos são triviais, nada precisa ser feito além de retornar falso comoresultado da operação! O terceiro caso ( X=a1) também é bastante simples de ser resolvido.Na verdade, nós teremos um pouco mais de dificuldade apenas no último caso, mesmo assim,já vimos que procurar um certo elemento numa lista ordenada é bastantes simples.

O algoritmo completo para remoção em lista ordenada está codificado a seguir. Noteque o comando free é executado sempre que um elemento é removido. Isto faz com que asáreas de memória que não são mais necessárias sejam colocadas novamente à disposiçãopara futura alocação pelo comando malloc. Desta forma, garantimos que enquanto houvermemória não utilizada, novos elementos poderão ser inseridos na lista ordenada.

int Remover (elem x){LstOrd P, Q;

if ( ( Anular() ) || ( x < L->obj) )return(0); /* 1o e 2o casos */

else{if ( x == L->obj ) /* 3o caso */

{P = L ;L = L->prox;free(P);return(1);}

else{P = L; /* 4 caso */while ( ( P->prox != NULL ) && ( x > P->prox->obj ) )

P = P->prox;if ( ( P->prox != NULL ) && ( x == P->prox->obj ) )

{Q = P->prox;P->prox = Q->prox;free(Q);return(2);}

elsereturn(0);

} /* fim else x == L->obj */} /* fim else Anular */

} /* fim funcao */

10.1.3 A Operação de Pesquisa

Dada uma lista ordenada L e um elemento X, a operação Procurar(X) verifica em L aexistência de X. Caso o elemento X seja encontrado, a operação resulta num valor através doqual é possível acessá-lo, senão, um valor especial é retornado para sinalizar o fracasso dabusca. Assim, quando o elemento for encontrado, verdadeiro será o valor de retorno daoperação, caso contrário, a função retornará falso para indicar que a pesquisa falhou:

80

int Procurar (elem x){LstOrd P;

P = L ;

while ( ( P != NULL ) && ( x > P->obj ) )P = P->prox;

if ( ( P != NULL ) && ( x == P->obj ) )return(1);

elsereturn(0);

}

10.1.4 Imprimindo uma Lista Ordenada

Para observar os elementos contidos numa lista ordenada, seria interessante dispor deuma rotina que, dada uma lista L, a imprimisse no vídeo do computador. Através desta rotinapoderíamos então ter acesso ao conjunto completo de valores armazenados na lista.

O formato de impressão a ser escolhido, naturalmente depende do tipo dasinformações manipuladas e da aplicação propriamente dita. Por exemplo, se a lista ordenadaarmazena os nomes dos convidados de uma festa, poderíamos imprimir um elemento por linha.Aqui, entretanto, seremos consistentes com a notação já utilizada.

void Mostrar( ){LstOrd P;

P = L ;

printf("\nLista: [ ");while ( P != NULL)

{printf("%c , ", P->obj);P = P->prox;}

printf(" ]");

}

10.1.5 Destruindo uma Lista Ordenada

Considere uma rotina dentro da qual é utilizada uma lista encadeada cujos nodos sãoalocados dinamicamente. Para se poder acessar o primeiro nodo da cadeia, certamente seránecessário usar uma variável ponteiro local à rotina, conforme exemplificado a seguir:

# include <stdio.h>#include <stdlib.h>

void main (){LstOrd P;Criar(P);Inserir(‘b’);Inserir(‘d’);Inserir(‘c’);Inserir(‘a’);Mostrar();}

81

Durante a execução da rotina, seria criada urna lista encadeada contendo quatronodos, sendo o endereço do nodo inicial aquele armazenado na variável P:

Como P é uma variável local, ela será automaticamente destruída ao término daexecução da rotina main(). Entretanto, os nodos pertencentes à cadeia, sendo variáveisdinâmicas, somente serão liberados através de um comando explícito (free). Desta forma, apósa execução da rotina, teremos quatro nodos “perdidos” na memória. Para resolver o problema,vamos desenvolver uma rotina que, dada uma lista encadeada L, libera todos os seus nodos.

Devemos lembrar que não é possível liberar diretamente o primeiro nodo, poisperderíamos o acesso ao resto da cadeia. Assim, vamos precisar de uma variável auxiliar Ppara guardar o endereço de um nodo até que ele possa ser liberado.

int Destruir(void){LstOrd P;

while ( L != NULL){P = L ;L = L->prox;free(P);}

return(1);}

Com esta nova operação, podemos agora liberar todos os nodos de uma listaencadeada, assim que ela não for mais necessária em uma certa aplicação.

Vale lembrar que vetores são automaticamente liberados quando saem do escopo emque foram definidos, isto torna desnecessário definir operações de destruição para estruturasimplementadas com alocação estática. Entretanto, toda implementação baseada em alocaçãodinâmica deve oferecer uma operação de destruição, que será chamada explicitamente todavez que uma variável criada não for mais necessária na aplicação.

De qualquer forma, após a execução total de um programa, o sistema operacionalrecupera automaticamente qualquer espaço de memória que tenha sido alocado por ele e quenão foi liberado explicitamente. O problema dos nodos perdidos só ocorre durante a execuçãodo programa, que pode ser interrompida devido à insuficiência de memória.

10.2 Técnicas de EncadeamentoAo utilizar alocação encadeada, precisamos lançar mão de alguns artifícios que

venham facilitar a manipulação das estruturas desenvolvidas. dependendo das operações aserem efetuadas sobre a lista encadeada, ter simplesmente um ponteiro para o nodo inicialpode não ser o suficiente se esperamos maior eficiência. Este capítulo apresenta algumastécnicas que poderão ser muito úteis.

10.2.1 Nodos Cabeça e Sentinela

Um nodo cabeça é um nodo extra mantido sempre na primeira posição de uma listaencadeada. Ele não é usado para armazenar um elemento da lista, tendo como único objetivosimplificar os procedimentos de inserção e remoção.

Numa implementação que use nodo cabeça, toda lista encadeada tem sempre pelomenos um nodo, desta forma, uma lista L vazia passa a ter outra representação:

82

Figura 10.2: Lista vazia com nodo cabeça

Vejamos como esta pequena alteração poderá tornar mais simples os procedimentosde inserção e remoção em lista ordenada. Comecemos pela operação de inicialização. Nestanova representação, ela não se resume apenas em anular o ponteiro inicial da cadeia:

int Criar (){L = (LstOrd *) malloc ( sizeof (LstOrd) ) ;

L->prox = NULL ;return(1);}

Como toda lista terá sempre um nodo cabeça, que nunca pode ser removido, todas asoperações de inserção e remoção serão realizadas em nodos a partir da segunda posição.

int Inserir (elem x){LstOrd N;


N->obj = x;

while ( (L->prox != NULL) && (x > L->prox->obj) )L = L->prox;

N->prox = L->prox;L->prox = N;return(1);}

Observe que, como os novos elementos não podem entrar antes do nodo cabeça, ainserção fica reduzida a um único caso: o elemento será inserido no meio ou no fim da lista.Assim, basta procurar a posição correta para inserção (com o laço while) e atualizar asligações. Também a remoção será reduzida a procurar o elemento no resto da lista e atualizaras ligações relevantes.

int Remover (elem x){LstOrd P;

while ( (L->prox != NULL) && (x > L->prox->obj) )L = L->prox;

if ( (L->prox != NULL) && (x == L->prox->obj) ){P = L->prox;L->prox = P->prox;free(P);return(1);}

elsereturn(0);

} /* fim funcao */

Dependendo da implementação, o nodo cabeça pode ser usado para guardar

83

informações gerais a respeito da lista encadeada. Um caso bastante comum é o uso do nodocabeça para armazenar o número de elementos contidos na lista. Naturalmente, cada vez queum nodo é inserido ou removido, o campo de dados do nodo cabeça deve ser atualizado.

Figura 10.3: Lista L:[a, b, c, d] com nodo cabeça contador.

Um nodo sentinela também é um nodo extra, porém este é mantido na última posiçãoda lista e armazena um valor especial chamado high value (HV), que deve ser o máximo entretodos aqueles que podem fazer parte da lista ordenada em questão. Por exemplo, supondouma lista cujos elementos são caracteres, o valor HV seria o código do último caractere databela ASCII: unsigned char HV = 255;

Nodos cabeça e sentinela, em conjunto, tornam os algoritmos ainda mais simples:

Figura 10.4: Lista vazia com nodos cabeça e sentinela.

Para inicializar a lista, precisamos alocar e encadear os dois nodos iniciais da estrutura:

int Criar (){L = (LstOrd *) malloc ( sizeof (LstOrd) ) ;L->prox = (LstOrd *) malloc ( sizeof (LstOrd) ) ;

L->prox->obj = HV;L->prox = NULL ;return(1);}

A rotina a seguir, implementa a operação de inserção em listas ordenadas com nodoscabeça e sentinela. Observe que a introdução do nodo sentinela permite eliminar o teste queverifica se o final da lista já foi atingido. Como HV é máximo, certamente o teste X>L->prox->obj tornar-se-á falso antes que seja atingido o fim da lista encadeada!

int Inserir (elem x){LstOrd N;


N->obj = x;

while ( x > L->prox->obj )L = L->prox;

N->prox = L->prox;L->prox = N;return(1);}

Nada impede que um elemento inserido na lista tenha o mesmo valor de HV.Entretanto, ao remover um nodo da cadeia, devemos nos certificar de que ele não seja o nodosentinela. Para isto é que serve o teste L->prox->prox != NULL; qualquer nodo pode armazenaro valor de HV, mas somente o nodo sentinela tem um ponteiro nulo!

84

int Remover (elem x){LstOrd P;

while ( x > L->prox->obj )L = L->prox;

if ( (L->prox->prox != NULL) && (x == L->prox->obj) ){P = L->prox;L->prox = P->prox;free(P);return(1);}

elsereturn(0);

} /* fim funcao */

Também, durante a operação de pesquisa, precisamos ter certeza de que o nodoencontrado não é o nodo sentinela, já que ele não faz parte dos elementos da lista.

10.3 Encadeamento circularNuma lista com encadeamento circular, ao invés do campo de ligação do último nodo

armazenar um endereço nulo, ele armazena o endereço do primeiro nodo:

Figura 10.5: Lista encadeada circular

Como o endereço do primeiro nodo pode ser facilmente obtido através do campo deligação do último nodo, a variável ponteiro para uma lista circularmente encadeada guarda nãoo endereço do primeiro, mas sim do último nodo da cadeia.

A grande vantagem em se usar encadeamento circular é que podemos acessarrapidamente tanto o primeiro quanto o último nodo da lista. Na implementação não circular,acessar o último elemento requer a passagem por todos os elementos da cadeia, um a um, atéatingir o último. Por exemplo, se resolvemos implementar filas com listas encadeadas, aoperação de remoção seria rápida (primeiro elemento), entretanto a operação de inserção seriabastante lenta (último elemento).

Veja a seguir, a implementação de filas usando listas circularmente encadeadas.Primeiro vamos definir a organização dos dados:

typedef char elem;

typedef struct nodo *Fila;

struct nodo{elem obj;Fila prox;};

A inicialização e teste de fila vazia são triviais na implementação com listas circulares.Note que não há necessidade de teste de fila cheia, já que estamos usando alocação dinâmicade memória:

85

void IniciaFila ( Fila F){

F = NULL;

}

int FilaVazia (Fila F){if (F == NULL)

return(1);else

return(0);

Ao ser inserido na fila, um novo nodo deverá sempre armazenar o endereço doprimeiro elemento na lista encadeada. Se a fila estava vazia antes da inserção, então o novonodo terá que apontar para si mesmo.

int Inserir (Fila F, elem x){Fila N;


N->obj = x;

if ( FilaVazia(F) ){F = N;N->prox = N;}

else{N->prox = F->prox;F->prox = N;F = N;}

return(1);

Ao remover um elemento, devemos estar atentos para o caso de a fila ter somente oelemento que vai ser removido, pois, neste caso, a fila tornar-se-á vazia.

elem Retirar (Fila F){Fila P;

if ( ! FilaVazia(F) ){if ( F == F->prox )

{Retirar = F->obj;free(F);F = NULL;}

else{P = F->prox;F->prox = P->proxRetirar = P->obj;free(P);}

}else

86

printf("Underflow !");

Analise o código apresentado e veja como o encadeamento circular tornou aimplementação muito mais eficiente do que ela seria se tivéssemos usado uma lista encadeadacomum.

10.4 Encadeamento Duplo

Numa lista com encadeamento duplo, cada nodo tem dois campos de ligação sendoque um deles armazena o endereço do nodo predecessor e o outro armazena o endereço dosucessor:

Figura 10.6: Lista duplamente encadeada.

Sendo cada nodo da forma (esq, obj, dir), dado um ponteiro P que armazena oendereço de um nodo qualquer no meio da lista, vale a seguinte igualdade: “P = P->esq->dir =P->dir->esq” .

Por exemplo, na figura 10.6, se partimos do ponteiro P e vamos para a esquerda edepois para a direita, retornamos ao mesmo nodo de partida. Assim, esta igualdade caracterizaa principal propriedade de uma lista duplamente encadeada, que é a facilidade de retrocederou avançar na cadeia, a partir de um determinado nodo, com a mesma eficiência.

Entretanto, a igualdade não se verifica se P estiver apontando um nodo extremo dalista. Por exemplo, se P aponta o primeiro nodo da lista, que não tem predecessor, então não épossível ir para a esquerda e depois voltar à direita. Por este motivo, listas duplamenteencadeadas normalmente são implementadas de forma circular; pois, neste caso, an precedea1 e a1 sucede an. A existência de um nodo sentinela garante a validade da igualdade mesmoestando a lista vazia e, portanto, torna a estrutura ainda mais uniforme.

Figura 10.7: Encadeamento duplo circular com sentinela.

Em termos práticos, uma lista duplamente encadeada permite o acesso aos seusnodos tanto da esquerda para a direita quanto da direita para a esquerda. Supondo uma listaordenada, com a estrutura apresentada na figura 10.7, então podemos acessar os seuselementos tanto em ordem crescente quanto decrescente, sempre com a mesma eficiência.

Se o encadeamento duplo tem a desvantagem de gastar mais memória, por outro lado,tem a vantagem de ser mais flexível e de tornar as operações básicas mais elegantes. Sendo Pum ponteiro para um nodo qualquer no meio de uma lista duplamente encadeada, e N umponteiro para um novo nodo a ser inserido antes de P, podemos usar as seguintes instruções:

N->esq = P->esq;N->dir = P;P->esq->dir = N;P->esq = N;

87

Para remover o nodo apontado por P, fazemos:

P->esq->dir = P->dir ;p->dir->esq = P->esq;free (P);

88

Bibliografia

[Aze 96] Azeredo, Paulo A. . Método de Classificação de dados e análise de suascomplexidades. Editora Campus. Rio de Janeiro. 1996.

[Per 96] Pereira, Silvio Lago. Estrutura de dados Fundamentais: conceitos eaplicações. Editora Érica. São Paulo. 1996

[Szw 94] Szwarcfiter, Jaime Luiz, Markenzon, Lilian. Estruturas de dados e seusalgoritmos. Editora Livros Tecnicos e Científicos. Rio de Janeiro. 1994.

[Ten 95] Tenenbaum, Aaron M.. Estruturas de dados usando C. Editora MakronBooks, São Paulo.1995.

[Vel 83] Veloso, Paulo, Santos, Clesio dos, Azeredo, Paulo, Furtado, Antonio.Estrutura de Dados. Editora Campus, Rio de Janeiro. 1998.

89

Documents

Ordenacao - Aed II c Pas