Prévia do material em texto

144
Unidade IV
Unidade IV
7 VETORES, MATRIZES E ESTRUTURAS
Um dos elementos-chave no design de software é determinar quais estruturas de dados são 
mais apropriadas para o problema em questão. As estruturas de dados determinam como as 
informações são armazenadas e trocadas e possuem um efeito significativo na coesão, na clareza 
e na eficiência do programa.
7.1 Matrizes
Manzano (2015, p. 181) ressalta que “uma variável simples de certo tipo ocupa um bloco de 
memória onde tal valor será armazenado, enquanto uma variável composta ocupa um conjunto 
de blocos do tipo definido”.
A mais simples de todas as estruturas de dados é a matriz. Ela é suportada pela linguagem C e 
define uma sequência contígua de elementos na memória, agrupando um conjunto de variáveis do 
mesmo tipo e permitindo a iteração sobre o conjunto.
 Observação
Cada item de dados de uma matriz é chamado de elemento e cada 
elemento é único e localizado em um local específico da memória. Uma 
matriz pode ser unidimensional ou multidimensional e o número de 
subscritos determina sua dimensão. Uma matriz dimensional é conhecida 
como vetor e as matrizes bidimensionais são conhecidas como matriz.
7.1.1 Matriz unidimensional
Vejamos mais uma vez o que diz Manzano:
 
Esse tipo de estrutura de dados é conhecido como matriz de uma dimensão, 
vetor, arranjo, variável composta, variável indexada, entre outras formas. É 
usado comumente na criação de tabelas simples. A matriz usa uma única 
variável, que tem determinado tamanho, e pode armazenar mais de um 
valor (conhecido como elemento). O tamanho de uma matriz é conhecido 
como dimensão, constituída por constantes inteiras e positivas. Os nomes 
dados às matrizes seguem as mesmas regras de nomes atribuídos a variáveis 
simples (MANZANO, 2015, p. 181).
145
ALGORITMOS
No exemplo a seguir, vamos implementar um programa para calcular a média geral de oito 
médias de cada aluno. Dessa forma, será necessário criar uma única variável indexada (a matriz) 
contendo todos os valores das oito médias (cada posição de armazenamento de uma matriz é 
conhecida como slot).
A) 
B) 
Figura 66 – Matriz unidimensional (imagem do programa Dev C++)
Exemplo de aplicação
Pesquise sobre a importância da utilização dos princípios da matriz unidimensional no 
desenvolvimento de projetos.
146
Unidade IV
O próximo exemplo tem como objetivo ler oito elementos de uma matriz A do tipo vetor. Para 
isso, é preciso construir uma matriz B de mesmo tipo, observando a seguinte lei de formação: se 
o valor de um elemento da matriz A estiver numa posição de índice par, ele deve ser multiplicado 
por 5; se o valor de um elemento da matriz A estiver numa posição de índice ímpar, ao elemento 
de A deve-se somar 5.
A) 
B) 
Figura 67 – Matriz unidimensional (imagem do programa Dev C++)
147
ALGORITMOS
 Saiba mais
Para conhecer mais detalhes sobre a matriz unidimensional, você pode 
ler a obra indicada a seguir.
PAES, R. de B. Introdução à programação com a linguagem C: aprenda a 
resolver problemas com uma abordagem prática. São Paulo: Novatec, 2016.
7.1.2 Matriz bidimensional
Sobre esse tema, retomemos algumas palavras de Manzano.
 
Em matrizes com mais de uma dimensão, os elementos também são 
manipulados individualmente, sendo a referência feita sempre por meio de 
dois índices: o primeiro para indicar a linha; o segundo, a coluna. Dessa 
forma, TABELA [2][3] indica uma referência ao elemento armazenado na linha 2 
e na coluna 3. A linguagem de programação C não trabalha diretamente 
com matrizes que tenham mais de uma dimensão, como outras linguagens 
fazem, mas permite a simulação perfeita desse efeito. Isso ocorre porque 
essa linguagem trabalha com matrizes de matrizes, ou seja, uma matriz 
considerada de duas dimensões é, na verdade, uma matriz cujos elementos 
são outra matriz (MANZANO, 2015, p. 186).
No exemplo a seguir, temos uma matriz com duas dimensões. O programa realiza a entrada e a 
saída das quatro notas bimestrais de dez alunos.
148
Unidade IV
A) 
B) 
Figura 68 – Matriz bidimensional (imagem do programa Dev C++)
Exemplo de aplicação
Pesquise sobre a importância da utilização dos princípios da matriz bidimensional no 
desenvolvimento de projetos.
149
ALGORITMOS
No caso a seguir, o programa apresenta os dados dos alunos de forma sequencial. Assim, só é 
possível visualizar as notas dos últimos alunos.
A) 
B) 
Figura 69 – Matriz unidimensional (imagem do programa Dev C++)
 Lembrete
Uma matriz é a coleção de tipos de dados semelhantes ou coleção de 
entidades semelhantes armazenadas em local de memória contígua.
150
Unidade IV
7.1.3 Matriz interna
Quanto a esse assunto, Manzano ressalta que:
 
A definição de matrizes internas é útil quando o programa necessita 
possuir internamente tabelas de valores para serem consultadas pelo 
próprio programa. Isso dará para eferivação de certo processamento sem a 
participação do usuário do programa (MANZANO, 2015, p. 189).
A seguir, temos um programa que apresentará os valores da matriz denominada Valores, além 
do tamanho que tal matriz ocupa na memória e a quantidade de elementos armazenados.
A) 
B) 
Figura 70 – Matriz interna (imagem do programa Dev C++)
151
ALGORITMOS
Exemplo de aplicação
Pesquise sobre a importância da utilização dos princípios da matriz interna no desenvolvimento 
de projetos.
No próximo exemplo, vemos a utilização de tabelas de valores em uma matriz unidimensional 
com tamanho implícito, que apresentará os valores da matriz Valores, o tamanho que tal matriz 
ocupa na memória e a quantidade de elementos armazenados.
A) 
B) 
Figura 71 – Matriz interna (imagem do programa Dev C++)
152
Unidade IV
7.2 Estruturas
Vejamos o que diz Damas:
 
As estruturas em C (que correspondem aos registros em outras linguagens) 
permitem colocar, em uma única entidade, elementos de tipos diferentes. 
Uma estrutura é um conjunto de uma ou mais variáveis (às quais vulgarmente 
também se chamam campos ou membros) agrupadas sob um único nome, 
de forma a facilitar a sua referência. As estruturas podem conter elementos 
com qualquer tipo de dados válidos em C (tipos básicos, vetores, strings, 
ponteiros ou mesmo outras estruturas) (DAMAS, 2016, p. 266).
 Observação
Assim como as variáveis primárias, as variáveis de estrutura também 
podem ser inicializadas quando são declaradas. Os modelos de estrutura podem 
ser definidos de forma local ou global. Caso a opção escolhida seja local, a 
variável pode ser usada dentro dessa função; se for global, pode ser usada 
por todas as outras funções do programa.
7.2.1 Estruturas e typedef
Ainda segundo Damas:
 
Para declarar uma variável do tipo struct Data [...] basta indicar qual o tipo 
(struct Data) seguido do nome das variáveis struct Data d, datas[100], 
*ptr_data, em que :
• d é uma variável do tipo struct Data;
• datas é um vetor de 100 elementos, sendo cada um deles uma 
estrutura do tipo struct Data;
• ptr_data é um ponteiro para o tipo struct Data (DAMAS, 2016, p. 266).
O código a seguir apresenta uma função que permite escrever na tela os valores existentes em 
uma estrutura recebida como argumento.
153
ALGORITMOS
A) 
B) 
Figura 72 – Estruturas e typedef (imagem do programa Dev C++)
Exemplo de aplicação
Pesquise sobre a importância da utilização das estruturas no desenvolvimento de projetos.
No próximo exemplo, iremos realizar o carregamento de uma estrutura através de uma função. 
Como será possível alterar os valores presentes na estrutura, teremos que passar a essa função o 
endereço da estrutura que queremos ler.
154
Unidade IV
A) 
B) 
Figura 73 – Estruturas e typedef (imagem do programa Dev C++)
Para Damas:
 
Em C, um vetor permite agrupar, sob uma mesma variável, um conjunto 
de elementos, sendo obrigatoriamente todos do mesmo tipo. As estruturas 
155
ALGORITMOS
permitem agrupar diversos componentes em uma única variável, que 
podem ser definidos com tipos distintos.Para evitar a repetição da palavra struct na declaração de variáveis, é 
possível definir um novo tipo de dados utilizando a palavra reservada 
typedef. A definição de novos tipos terá que ser sempre realizada a partir 
de tipos já existentes, definindo assim um sinônimo, isto é, uma outra forma de 
referência a esse tipo (DAMAS, 2016, p. 279).
 Saiba mais
Para conhecer mais detalhes sobre a aplicação de estruturas, leia o livro 
indicado a seguir.
MIZRAHI, V. V. Treinamento em linguagem C. São Paulo: Pearson, 2008.
8 ALGORITMOS DE BUSCA E ORDENAÇÃO
Na ciência da computação, um algoritmo de classificação é um algoritmo que coloca os 
elementos de uma lista em uma determinada ordem. As ordens mais usadas são a ordem numérica 
e ordem alfabética. A classificação eficiente é importante para otimizar o uso de outros algoritmos 
(como algoritmos de busca e mesclagem) que exigem que as listas classificadas funcionem 
corretamente; também é útil para organizar os dados e produzir resultados legíveis por humanos. 
Mais formalmente, a saída deve satisfazer duas condições específicas:
• a saída está em ordem não decrescente (cada elemento não é menor que o elemento anterior, de 
acordo com o pedido total desejado);
• a saída é uma permutação ou reordenação da entrada.
Desde o início da computação, o problema de classificação atraiu uma grande quantidade de 
pesquisas, talvez devido a sua alta complexidade de resolver a questão com eficiência, apesar de sua 
declaração simples e familiar.
 Lembrete
A classificação é um processo que organiza uma coleta de dados em 
ordem crescente ou em ordem decrescente.
156
Unidade IV
8.1 Algoritmos de ordenação
Diz Manzano:
 
Uma das atividades mais requisitadas no trabalho de programação é, sem 
dúvida, a ordenação do conteúdo (elementos) das tabelas (matrizes). Existem 
diversas técnicas de ordenação que podem ser implementadas em um programa 
de computador, tais como inserção direta, inserção direta com busca binária, 
incremento decrescente (shellsort), bolha (bubblesort), agitação (shakesort), 
pente (combsort), partição e troca (quicksort), seleção direta, seleção em árvore 
(heapsort), árvore amarrada (threaded heapsort), indexação direta (radixsort), 
intercalação simples (mergesort) e listas de colisões (MANZANO, 2015, p. 219).
A classificação é o processo de reorganizar uma sequência de objetos para colocá-los em 
alguma ordem lógica, como a ordem alfabética ou a ordem numérica. Como a onipresença do 
uso do computador nos deixou inundados de dados, a primeira etapa para organizá-los é, muitas 
vezes, classificá-los. Todos os sistemas de computador possuem implementações de algoritmos de 
classificação, para a utilização do sistema e pelos usuários.
A classificação e a ordenação têm se mostrado duas áreas de profundo interesse para 
pesquisadores algorítmicos, com muitos recursos sendo estudados para encontrar as melhores 
práticas e resultados. Vale ressaltar que a classificação desempenha um papel importante nos 
dados comerciais, no processamento e na computação científica moderna.
Os aplicativos são abundantes no processamento de transações, otimização combinatória, 
astrofísica, dinâmica molecular, linguística, genômica, previsão do tempo e muitos outros campos. 
De acordo com Aho, Hopcroft e Ullman (1974), a classificação foi considerada como um problema 
fundamental no estudo de algoritmos por várias razões. Algumas delas são listadas a seguir:
• a necessidade de classificar as informações é inerente aos muitos aplicativos;
• os algoritmos costumam usar a classificação como uma chave em sua sub-rotina.
No projeto de algoritmos, existem muitas técnicas representadas no corpo de classificação e 
ordenação de algoritmos.
 Observação
Uma classificação interna requer que a coleta de dados caiba 
inteiramente na memória principal do computador. Podemos usar 
uma classificação externa quando a coleta de dados não se encaixa na 
memória principal do computador de uma só vez, devendo residir em um 
armazenamento secundário (como um disco).
157
ALGORITMOS
O código a seguir ordena cinco valores inteiros. Observe que é utilizado o processo de integração 
dos comandos quando for encadeado.
Figura 74 – Ordenação de números (imagem do programa Dev C++)
Exemplo de aplicação
Pesquise sobre situações em que podemos utilizar a ordenação de números no desenvolvimento 
de projetos.
O código a seguir irá classificar (ordenar) uma cadeia de caracteres representando 
nomes próprios e, após o processamento da ordenação, apresentará tal cadeia em ordem 
alfabética ascendente.
158
Unidade IV
A) 
B) 
Figura 75 – Ordenação de texto (caracter) (imagem do programa Dev C++)
159
ALGORITMOS
A classificação é um algoritmo que organiza os elementos em ordem crescente ou decrescente. 
Assim, os algoritmos de classificação podem diminuir a complexidade de um problema. Podemos 
elencar dois tipos de classificação: a classificação interna e a classificação externa.
Os algoritmos de classificação podem ser agrupados com base nos seguintes parâmetros:
• Estabilidade: de acordo com Elisseeff, Theodoros e Massimiliano (2005), um algoritmo de 
classificação é estável se preserva a forma de chaves duplicadas ou se o termo estabilidade 
significa que esses elementos semelhantes retêm suas posições de forma relativísticas após 
a classificação.
• Adaptabilidade: Estivill-Castro e Wood (1992) afirma que um algoritmo de classificação é 
adaptativo caso ele consiga classificar as sequências que estão próximas de serem classificadas 
mais rapidamente do que as sequências aleatórias. Com alguns algoritmos de classificação, a 
complexidade muda com base na pré-classificação (classificação rápida): a pré-classificação da 
entrada afeta o funcionamento (e o seu tempo de processamento).
• Complexidade de tempo: a complexidade de tempo de um algoritmo significa o tempo total 
exigido pelo programa para ser executado até a sua conclusão. De acordo com Cormen et al. 
(2009), a complexidade de tempo de um algoritmo é representada pelas notações assintóticas, 
uma vez que elas fornecem os limites inferior e superior de um algoritmo.
• Complexidade do espaço: a complexidade espacial de qualquer algoritmo também é 
importante, correspondendo ao número de células de memória de que ele precisa. Cormen 
et al. (2009) afirmam que a complexidade do espaço deve ser calculada levando-se em conta 
tanto o espaço auxiliar quanto o espaço usado pela entrada.
A partir desses princípios podemos observar o funcionamento de alguns algoritmos de 
classificação bem como sua complexidade e estabilidade. A seguir, iremos discutir sobre os 
seguintes algoritmos:
• Bubble Sort;
• Selection Sort;
• Insertion Sort;
• Merge Sort;
• Quick Sort.
Bubble Sort
A classificação Bubble Sort tem O (n) como o melhor caso de desempenho e O (n * n) como 
o desempenho de pior caso. A classificação Bubble Sort deve realizar uma comparação de 
160
Unidade IV
grande número quando há mais elementos em uma lista e aumenta à medida que aumenta o 
número de itens que precisam ser classificados. Embora a classificação por bolha seja muito fácil 
de implementar, é ineficiente em comparação com todos os outros algoritmos de classificação. 
Trata-se do algoritmo de classificação mais simples que funciona frequentemente com a troca dos 
elementos vizinhos se eles estiverem na ordem errada.
 
O método de ordenação bolha é bastante simples, e talvez seja o método de 
ordenação mais difundido. Uma iteração do mesmo se limita a percorrer a 
tabela do início ao fim, sem interrupção, trocando de posição dois elementos 
consecutivos sempre que estes se apresentem fora de ordem. Intuitivamente 
percebe-se que a intenção do método é mover os elementos maiores em 
direção ao fim da tabela. Ao terminar a primeira iteração, pode-se garantir 
que as trocas realizadas posicionam o maior elemento na última posição. 
Na segunda iteração, o segundo maior elemento é posicionado, e assimsucessivamente. O processamento é repetido então n – 1 vezes. O algoritmo 
que se segue implementa esse método. A tabela se encontra armazenada 
na estrutura L. O algoritmo ordena L segundo valores não decrescentes do 
campo chave (SZWARCFITER, 2015, p. 159, grifo do autor).
Selection Sort
A classificação Selection Sort é o tipo de algoritmo mais simplista, no entanto, mostra-se 
ineficiente. Na classificação de seleção, temos que encontrar o menor elemento fazendo a varredura 
linear e mover esse elemento para a frente (trocando-o com o elemento frontal). Então, temos que 
encontrar o segundo menor elemento e movê-lo de seu lugar, novamente fazendo uma varredura 
linear. É necessário continuar fazendo isso até que todos os elementos estejam em seus lugares.
Esse algoritmo também mantém duas submatrizes em uma determinada matriz: a primeira submatriz 
que já está classificada e a segunda restante (denominada submatriz) que não está classificada. A cada 
iteração de classificação de seleção, o menor elemento do secundário não classificado da matriz é 
escolhido e movido para a matriz secundária classificada.
Insertion Sort
A classificação por inserção é uma classificação de comparação simples, mas eficiente, para 
pequenos dados. A classificação por inserção é reduzida ao seu número total de etapas; se fornecida 
uma lista parcialmente classificada, terá uma maior eficiência. É praticamente mais eficiente do 
que a classificação por seleção e uma classificação por bolha, mesmo que todos eles tenham 
complexidade de pior caso: O (n * n).
Os números são divididos em classificados e não classificados. Os valores não classificados são 
colocados em suas posições adequadas na matriz secundária classificada, um por um.
161
ALGORITMOS
O algoritmo Insertion Sort é bem organizado para conjuntos de dados menores, mas pouco 
viável para listas maiores. Ele reduz o número total de etapas se receber uma lista parcialmente 
classificada, aumentando a eficiência.
 
O método de ordenação por inserção é também bastante simples, sendo 
sua complexidade equivalente à da ordenação bolha. Imagine uma tabela já 
ordenada até o i-ésimo elemento. A ordenação da tabela pode ser estendida 
até o (i + 1)-ésimo elemento por meio de comparações sucessivas deste com 
os elementos anteriores, isto é, com o i-ésimo elemento, com o (i – 1)-ésimo 
elemento etc., procurando sua posição correta na parte da tabela que já está 
ordenada. Pode-se, então, deduzir um algoritmo para implementar o método: 
consideram-se sucessivamente todos os elementos, a partir do segundo 
deles, em relação à parte da tabela formada pelos elementos anteriores ao 
elemento considerado em cada iteração (SZWARCFITER, 2015, p. 159).
Merge Sort
O algoritmo Merge Sort divide a matriz de entrada em duas seções, chamando a si mesmo 
para as duas divisões e mesclando duas divisões ordenadas. A seguir, são descritos os processos a 
serem realizados
• Divide Step: se um dado vetor (ou array) possuir zero ou um elemento, simplesmente retorne 
esse valor. Caso contrário, o algoritmo deve dividir o vetor, por exemplo Vetor1 [x ... z], em duas 
matrizes secundárias Vetor1 [x ... z] e Vetor2 [y + 1 ... z], cada uma contendo cerca de partes dos 
elementos de Vetor1 [x ... z]. Ou seja, y é o ponto intermediário de Vetor1 [x ... z].
• Conquer Step: agora classificando as duas pequenas matrizes Vetor1 [x ... z] e Vetor2 [y + 1 ... z], 
deve-se utilizar o método de recursidade usando o conquer.
• Combine Step: afinal, temos que mesclar a parte de trás do elemento em Vetor1 [x ... z] a 
partir das duas pequenas matrizes classificadas Vetor1 [x ... z] e Vetor1 [y + 1 ... z] em uma série 
classificada.
 
A ideia básica do método é intercalar as duas metades da lista desejada 
quando estas já se encontram ordenadas. Na realidade, deseja-se então 
ordenar primeiramente as duas metades, o que pode ser feito utilizando 
recursivamente o mesmo conceito.
Primeiramente, o processo de intercalação será revisto. Sejam duas listas 
A e B, ordenadas, com respectivamente n e m elementos. As duas listas são 
percorridas por ponteiros ptA e ptB, armazenando o resultado da intercalação na 
lista C, apontada pelo ponteiro ptC. O primeiro elemento de A é comparado 
com o primeiro elemento de B; o menor valor é colocado em C. O ponteiro 
da lista onde se encontra o menor valor é incrementado, assim como o 
162
Unidade IV
ponteiro da lista resultado; o processo se repete até que uma das listas seja 
esgotada. Neste ponto, os elementos restantes da outra lista são copiados 
na lista resultado.
Seja L a lista que se deseja ordenar. O método de ordenação por intercalação 
consiste em dividir a lista original em duas metades e ordená-las; o resultado 
são duas listas ordenadas que podem ser intercaladas. Para ordenar cada 
uma das metades o processo considerado é o mesmo, sendo o problema 
dividido em problemas menores, que são sucessivamente solucionados 
(SZWARCFITER, 2015, p. 159).
Quick Sort
O algoritmo Quick Sort é um dos algoritmos de classificação mais rápidos que faz parte de 
muitas bibliotecas de classificação. O tempo desse algoritmo depende muito da escolha do elemento 
pivô. O algoritmo Quick Sort também pertence à categoria de algoritmos de divisão e conquista e 
depende do funcionamento da partição.
Para particionar uma matriz, um elemento denominado pivô é selecionado. O algoritmo Quick 
Sort funciona da seguinte maneira:
• Vetor [j] = x é o valor pivô;
• Vetor [j… p - 1] contém elementos menores que x;
• Vetor [p + 1… r - 1] contém os elementos que são maiores ou equivalentes a x;
• Vetor [r ... k] contém elementos que ainda não foram explorados.
Como a seleção dos elementos do pivô é aleatória, o caso médio e o tempo de execução do 
melhor caso é O (n log n). Além disso, no pior caso de complexidade de tempo é O (n * n). Vale 
esclarecer que a classificação rápida não é um algoritmo de classificação estável.
 
O nome quicksort (ordenação rápida) já indica o que se deve esperar do 
método, que é, na realidade, um dos mais eficientes dentre os conhecidos. 
Dada uma tabela L com n elementos, o procedimento recursivo para ordenar 
L consiste nos seguintes passos:
• se n = 0 ou n = 1 então a tabela está ordenada;
• escolha qualquer elemento x em L – este elemento é chamado pivô;
163
ALGORITMOS
• separe L – {x} em dois conjuntos de elementos disjuntos: S1 = {w ∈ L – {x}|w 
< x} e S2 = {w ∈ L – {x}|w ≥ x}; o procedimento de ordenação é chamado 
recursivamente para S1 e S2;
• L recebe a concatenação de S1, seguido de x, seguido de S2.
Dois pontos são decisivos para o bom desempenho do algoritmo: a escolha 
do pivô e o particionamento da tabela. Esses pontos são analisados a seguir. 
A escolha do pivô mais utilizada é tomar o primeiro elemento como tal. 
Isto é aceitável se a tabela é reconhecidamente aleatória. Se, entretanto, a 
tabela está ordenada na ordem inversa à desejada, esta escolha provoca o 
pior desempenho do algoritmo. A partição obtida nesse caso separa a tabela 
de tal forma que o conjunto S1 contém n – 1 elementos e o conjunto S2 é 
vazio. Sendo assim, o primeiro elemento não é uma boa escolha para pivô.
Uma estratégia alternativa é a escolha aleatória do pivô, mas a geração 
de números aleatórios poderia pesar no tempo de execução. A situação 
ideal seria a escolha de um pivô tal que proporcionasse a partição da tabela 
em dois subconjuntos de dimensão equivalente. Para isso, a mediana da 
tabela deveria ser o elemento selecionado, lembrando que a mediana de 
um conjunto de n elementos é o n/2-ésimo maior número. Infelizmente, o 
cálculo desse elemento seria também muito custoso. Uma solução utilizada 
com bons resultados é a escolha da mediana dentre três elementos: o 
primeiro, o último e o central (SZWARCFITER, 2015, p. 159).
 Saiba mais
Para conhecer um pouco mais sobre a aplicação dos algoritmos de 
ordenação, leia a obra indicada a seguir:
DEITEL, P.; DEITEL, H. C: como programar.São Paulo: Pearson, 2015.
8.2 Algoritmos de busca
Vejamos o que diz Manzano:
 
A utilização de matrizes pode gerar grandes tabelas, dificultando a localização 
rápida de determinado elemento. Imagine uma matriz com 4.000 elementos 
(4.000 nomes de pessoas). Será que você conseguiria encontrar rapidamente 
um elemento desejado de forma manual, mesmo estando a lista de nomes 
em ordem alfabética? Certamente que não.
164
Unidade IV
Para solucionar esse problema, você pode fazer pesquisas em matrizes por 
meio de programação. Nesse sentido, dois métodos podem ser utilizados: 
pesquisa sequencial e pesquisa binária (MANZANO, 2015, p. 232).
Ao comparar o desempenho de dois algoritmos de pesquisa ou dois algoritmos de classificação, 
nos concentramos em dois tipos de operações: movimentos de dados e comparações. Os 
movimentos de dados ocorrem quando substituímos um item em uma lista por outro item da lista. 
As comparações de dados ocorrem quando comparamos um item em uma lista com outro item na 
lista ou a um item fora da lista.
 
Dado um conjunto de elementos, onde cada um é identificado por uma 
chave, o objetivo é localizar nesse conjunto o elemento correspondente 
a uma chave específica procurada [...] É importante ressaltar a relevância 
desse problema na área de computação, em especial nas aplicações não 
numéricas. Sem dúvida, a operação de busca é uma das mais frequentemente 
realizadas. (SZWARCFITER, 2015, p. 49).
 Observação
Existem dois tipos de algoritmos de pesquisa: os algoritmos que não 
fazem suposições sobre a ordem da lista e os algoritmos que assumem que 
a lista já está em ordem.
8.2.1 Pesquisa sequencial
Sobre a pesquisa sequencial, salienta Manzano:
 
O primeiro método [a pesquisa sequencial] busca a informação desejada 
sequencialmente, desde o primeiro elemento até o último.
Localizando a informação no caminho, ela é apresentada. Esse método de 
pesquisa é lento, mas eficiente nos casos em que os elementos de uma 
matriz encontram-se desordenados (MANZANO, 2015, p. 232).
Considere o programa a seguir, que recebe dez valores inteiros e concede ao usuário a 
possibilidade de pesquisar os valores armazenados.
165
ALGORITMOS
A) 
B) 
Figura 76 – Pesquisa sequencial (imagem do programa Dev C++)
166
Unidade IV
Exemplo de aplicação
Pesquise sobre situações em que podemos utilizar a pesquisa sequencial no desenvolvimento 
de projetos.
No próximo exemplo, é possível verificar a técnica de pesquisa sequencial para manipulação de 
dados alfanuméricos. Trata-se de um programa que recebeu dez nomes próprios e deve possibilitar 
ao usuário a realização de uma pesquisar entre esses nomes.
A) 
167
ALGORITMOS
B) 
Figura 77 – Pesquisa sequencial (imagem do programa Dev C++)
8.2.2 Pesquisa binária
Diz Manzano:
 
O segundo método de pesquisa é, em média, mais rápido que o primeiro, 
mas exige que a matriz esteja previamente classificada, pois ela “divide” a 
lista em duas partes e “procura” saber se a informação a ser pesquisada está 
acima ou abaixo da linha de divisão. Se estiver acima, por exemplo, a metade 
abaixo é desprezada. Em seguida, se a informação não foi encontrada, a 
lista é novamente dividida em duas partes, e o método pergunta se aquela 
informação está acima ou abaixo, assim ele executa a busca até encontrar 
ou não a informação pesquisada (MANZANO, 2015, p. 235).
Considere o programa a seguir, que apresenta a técnica de pesquisa binária a partir da solicitação 
de dez nomes. Após esse processo, é realizada a ordenação e, por fim, o usuário tem a possibilidade de 
pesquisar pelos nomes que foram armazenados previamente.
168
Unidade IV
A) 
169
ALGORITMOS
B) 
Figura 78 – Pesquisa binária (imagem do programa Dev C++)
 Resumo
Vimos que um dos elementos-chave no design de software é determinar 
quais estruturas de dados são mais apropriadas para o problema em questão. 
As estruturas de dados determinam como as informações são armazenadas 
e trocadas e possuem um efeito significativo na coesão, na clareza e na 
eficiência do programa.
Discutiu-se que a matriz é a mais simples de todas as estruturas de 
dados. Observou-se que a matriz é suportada pela linguagem C e define uma 
sequência contígua de elementos na memória. Ela agrupa um conjunto de 
variáveis do mesmo tipo e permite a iteração sobre o conjunto.
Na sequência, tratamos do funcionamento dos algoritmos de 
ordenação. Vimos que uma das atividades mais requisitadas no trabalho 
de programação é, sem dúvida, a ordenação do conteúdo (elementos) 
das tabelas (matrizes). Por fim, encerramos a unidade abordando a 
implementação dos algoritmos de busca.
170
Unidade IV
 Exercícios
Questão 1. Considere a seguinte linha de código em linguagem C:
int A[10];
Sobre a variável A, podemos dizer que se trata de:
A) Uma variável do tipo inteiro com limite de 10 algarismos.
B) Uma string unidimensional de 10 elementos.
C) Uma variável tipo char que armazena o caractere A.
D) Uma variável do tipo inteiro que armazena o número 10.
E) Uma área igual a 10 metros quadrados.
Resposta correta: alternativa B.
Análise da questão
No trecho apresentado, há uma declaração de variável. Temos o tipo, inteiro (int), o nome 
da variável, A, e, em seguida, os colchetes contendo o número 10, indicando se tratar de uma 
variável do tipo matriz unidimensional com 10 elementos. O número entre colchetes é o número 
de elementos da matriz unidimensional. Se tivéssemos uma sequência de dois números entre 
colchetes logo após o nome da variável, estaríamos tratando de uma matriz bidimensional. Vale 
ressaltar que, em linguagem C, não fazemos a declaração de variável juntamente com a atribuição 
de valores nessa variável.
Questão 2. Dois métodos de busca frequentemente implementados são a pesquisa sequencial 
e a pesquisa binária. Esses métodos podem ser aplicados no desenvolvimento de algoritmos ou em 
problemas da vida real, como os descritos a seguir.
I – Procurar um documento em uma pilha de papel, do primeiro documento ao último, 
nessa ordem.
II – Procurar uma palavra em uma lista dividindo-a ao meio sucessivas vezes.
III – Procurar uma foto em um álbum abrindo em páginas aleatórias.
171
ALGORITMOS
É usado o método de busca sequencial apenas em:
A) I.
B) II.
C) III.
D) I e II.
E) I e III.
Resposta correta: alternativa A.
Análise da questão
Na busca sequencial, é feita a procura pelo elemento desejado em uma lista, sequencialmente, 
do primeiro ao último elemento. Dividir a lista ao meio sucessivas vezes é uma aplicação do 
algoritmo de busca binária, enquanto procurar fotos em páginas aleatórias representa um método 
randômico (ou aleatório) de busca.
172
FIGURAS E ILUSTRAÇÕES
Figura 1
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores São 
Paulo: Érica, 2019. p. 18.
Figura 2
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013. p. 22.
Figura 3
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 39.
Figura 4
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013. p. 24.
Figura 5
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013. p. 26.
Figura 6
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 39.
Figura 7
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 39.
Figura 8
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 40.
Figura 9
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 40.
173
Figura 10
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 40.
Figura 11SOICHER, L.; VIVALDI, F. Algorithmic Mathematics. London: University of London, 2004. p. 8. Web-book. 
Disponível em: http://www.maths.qmul.ac.uk/~lsoicher/ambook.pdf. Acesso em: 5 fev. 2021.
Figura 12
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 51.
Figura 14
SOUZA, M. A. F. et al. Algoritmos e lógica de programação: um texto introdutório para a engenharia. 
São Paulo: Cengage, 2019. p. 200.
Figura 15
SOUZA, M. A. F. et al. Algoritmos e lógica de programação: um texto introdutório para a engenharia. 
São Paulo: Cengage, 2019. p. 199.
Figura 16
SOUZA, M. A. F. et al. Algoritmos e lógica de programação: um texto introdutório para a engenharia. 
São Paulo: Cengage, 2019. p. 206.
Figura 17
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 136.
Figura 18
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 138.
Figura 19
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 164.
174
Figura 20
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 176.
Figura 21
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 178.
Figura 22
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 179.
Figura 23
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 192.
Figura 24
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 194.
Figura 25
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 195.
Figura 26
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 200.
Figura 27
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 201.
Figura 32
MANZANO, J. A. N. G. Estudo dirigido de algoritmos. São Paulo: Érica, 2012. p. 61.
175
Figura 35
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013. p. 48.
Figura 38
MANZANO, J. A. N. G. Estudo dirigido de algoritmos. São Paulo: Érica, 2012. p. 67.
Figura 41
MANZANO, J. A. N. G. Estudo dirigido de algoritmos. São Paulo: Érica, 2012. p. 73.
Figura 44
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 114.
Figura 46
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 117.
Figura 49
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 123.
Figura 51
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 125.
Figura 54
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019. p. 133.
Figura 58
A) SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
Figura 59
A) SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
176
Figura 60
A) SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
Figura 61
A) MANZANO, J. A. N. G. Estudo dirigido de linguagem C. São Paulo: Érica, 2013.
Figura 62
A) MANZANO, J. A. N. G. Estudo dirigido de linguagem C. São Paulo: Érica, 2013..
Figura 63
A) MANZANO, J. A. N. G. Estudo dirigido de linguagem C. São Paulo: Érica, 2013.
Figura 64
A) MANZANO, J. A. N. G. Estudo dirigido de linguagem C. São Paulo: Érica, 2013.
Figura 65
A) SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
Figura 66
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 67
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 68
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 69
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 70
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
177
Figura 71
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 72
A) DAMAS, L. Linguagem C. Rio de Janeiro: LTC, 2016.
Figura 73
A) DAMAS, L. Linguagem C. Rio de Janeiro: LTC, 2016.
Figura 74
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 75
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 76
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
Figura 77
A) MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
REFERÊNCIAS
Textuais
AHO, A.; HOPCROFT, J.; ULLMAN, J. The design and analysis of computer algorithms. Boston: 
Addison-Wesley, 1974.
BEALE, E. M. L. Matrix generators and output analyzers. In: KUHN, H. W. (ed.). Proceedings of 
the princeton symposium on mathematical programming. Princeton: Princeton University 
Press, 1970. p. 25-36.
BROOKSHEAR, J. G. Computer science: an overview. Boston: Pearson, 2009.
CHARNTAWEEKHUN, K.; WANGSIRIPITAK, S. Visual programming using flowchart. 2006. 
178
CHRISTODOULOU, M. et al. Algorithmic and programming training materials for teachers. Krosno, 
2018. Disponível: https://www.codeit-project.eu/wp-content/uploads/CodeIT_O1_EN.pdf. Acesso 
em: 7 fev. 2021.
CORMEN, T. Algoritmos: teoria e prática. São Paulo: LTC, 2012.
CORMEN, T. et al. Introduction to algorithms. Massachusetts/London: MIT Press/Cambridge Press, 2009.
CREEGAN, J. B. Dataform: a model management system. Arlington: Ketron Inc., 1985.
DAMAS, L. Linguagem C. Rio de Janeiro: LTC, 2016.
DART, S. et al. Overview of software development environments. 1992. Disponível em: https://www.ics.
uci.edu/~andre/ics228s2006/dartellisonfeilerhabermann.pdf Acesso em: 7 fev. 2021.
DEITEL, P.; DEITEL, H. C: como programar. São Paulo: Pearson, 2015.
DIFFERENCE BETWEEN SOURCE CODE AND OBJECT CODE. 24 jan. 2018. Disponível em: https://www.
differencebetween.com/wp-content/uploads/2018/01/Difference-Between-Source-Code-and-Object-
Code.pdf. Acesso em: 25 abr. 2020.
ELISSEEFF, A.; THEODOROS, E.; MASSIMILIANO, P. Stability of randomized learning algorithms. Journal 
of Machine Learning Research, 2005.
ESTIVILL-CASTRO, V.; WOOD, D. A survey of adaptive sorting algorithms. ACM Computing Surveys, n. 
24, v. 4, p. 441-476, 1992.
HUMBLE, J. Entrega contínua: como entregar software de forma rápida e confiável. Porto 
Algre: Bookman, 2013.
LAKHWANI, K. (ed.). Fundamentals of data structures: DCAP201. Delhi: Lovely Professional University, 
2013. Disponível em: http://ebooks.lpude.in/computer_application/bca/term_3/DCAP201_
FUNDAMENTALS_OF_DATA_STRUCTURES.pdf. Acesso em: 7 fev. 2021.
MANZANO, J. A. N. G. Algoritmos: lógica para desenvolvimento de programação de computadores. São 
Paulo: Érica, 2019.
MANZANO, J. A. N. G. Estudo dirigido de algoritmos. São Paulo: Érica, 2012.
MANZANO, J. A. N. G. Estudo dirigido de linguagem C. São Paulo: Érica, 2013.
MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
MIZRAHI, V. V. Treinamento em linguagem C. São Paulo: Pearson, 2008.
179
OJO, A.; ESTEVEZ, E. Object-oriented analysis and design with UML training course. Tokyo:The United 
Nations University, 2005.
ORAM, E.; NAIK, B. Lecture note on programming in C. [ca. 2010]. Disponível em: http://www.vssut.
ac.in/lecture_notes/lecture1424354156.pdf. Acesso em: 7 fev. 2021.
PAES, R. de B. Introdução à programação com a linguagem C: aprenda a resolver problemas com uma 
abordagem prática. São Paulo: Novatec, 2016.
PRESSMAN, R. S. Engenharia de software. São Paulo: Makron Books, 1995.
SEBESTA, R. W. Conceitos de linguagens de programação. Porto Alegre: Bookman, 2011.
SLONNEGER, K.; KURTZ, B. L. Formal syntax and semantics of programming languages: a laboratory 
based approach. Nova York: Pearson, 1995.
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
SOICHER, L.; VIVALDI, F. Algorithmic mathematics. London: University of London, 2004. Web-book. 
Disponível em: http://www.maths.qmul.ac.uk/~lsoicher/ambook.pdf. Acesso em: 5 fev. 2021.
SOUZA, M. R. F. et al. Algoritmos e lógica de programação: um texto introdutório para a engenharia. 
São Paulo: Cengage, 2019.
STALLINGS, W. Computer organization and architecture, designing for performance Boston: Pearson, 2010.
SZWARCFITER, J. L. Estruturas de dados e seus algoritmos. São Paulo: LTC, 2015.
UNIVERSITY OF CRETE. Introduction to data types and structures. 2020. Disponível em: https://www.
csd.uoc.gr/~hy252/html/References/Introduction%20to%20Data%20Types%20and%20Structures.pdf. 
Acesso em: 7 fev. 2021.
WALIA, R. K. Algorithm & flowchart manual for students. Pauri: University of Horticulture and Forestry, 
2020. Disponível em: http://www.yspuniversity.ac.in/cic/algorithm-manual.pdf. Acesso em: 7 fev. 2021.
WIRTH, N. Algorithms and data structures. 1985. Disponível em: https://inf.ethz.ch/personal/wirth/
AD.pdf. Acesso em: 7 fev. 2021.
YANG, K. Data types. [s.d.]. Disponível em: https://www2.southeastern.edu/Academics/Faculty/
kyang/2017/Fall/CMPS401/ClassNotes/CMPS401ClassNotesChap06.pdf. Acesso em: 7 fev. 2021.
ZHIRKOV, I. Programação em baixo nível: C, assembly e execução de programas na arquitetura Intel 64. 
São Paulo: Novatec, 2018.
180
Informações:
www.sepi.unip.br ou 0800 010 9000