Técnicas de Programação

Prévia do material em texto

1 
 
Disci 
 
Resolução / Resposta 
Enunciado: 
 
Busca e ordenação 
 
A ordenação ou classificação de registros consiste em organizá-los em ordem crescente ou 
decrescente e assim facilitar a recuperação desses dados. A ordenação tem como objetivo 
facilitar as buscas e pesquisas de ocorrências de determinado elemento em um conjunto 
ordenado. Na computação existe uma série de algoritmos que utilizam diferentes técnicas 
de ordenação para organizar um conjunto de dados, eles são conhecidos como Métodos 
de Ordenação ou Algoritmos de Ordenação. A ordenação de elementos é algo essencial 
em diversos aspectos da sociedade, principalmente para as empresas. Se os dados já 
estiverem ordenados, mais rápido será o tempo de geração da informação para o usuário 
 
Fonte: VIANA, D. Conheça os principais algoritmos de ordenação. Treinaweb, 26 dez. 2016. Disponível em: 
<https://www.treinaweb.com.br/blog/conheca-os-principais-algoritmos-de-ordenacao/>. Acesso em 18 jan. 
2021. 
 
Neste contexto, você foi contratado por um armazém para elaborar um programa de 
ordenação de caixas de sapatos, que será realizado por um braço mecânico, em ordem 
crescente de numeração. O tempo de busca por uma informação em um conjunto de 
dados depende de como os dados estão organizados. Se os mesmos estiverem ordenados, 
haverá maior rapidez no processo de consulta. Segundo (Cormem 2022), para ordenar os 
dados podem ser utilizados diversos tipos de algoritmos de ordenação, tais como: Merge-
Sort, Quick-Sort, InsertionSort, Selection-Sort, e Bubble-Sort. 
 
No método insertion sort, a cada passo, o menor elemento é procurado para que seja 
inserido na sequência já ordenada. Essa procura pode ser realizada sequencialmente ou 
por busca binária. 
 
Fonte: CORMEN, T. H. et al. Introduction to Algoritms. Massachusetts Institute of 
Technology. 2. ed., 2002. 
 
Considerando o estudo de caso acima e o algoritmo insertion sort para sua solução, 
responda: 
 
1- Escreva o algoritmo insertion sort, considerando uma busca sequencial. 
 
2- Considerando que as caixas do armazém já estão ordenadas, seguindo o algoritmo 
insertion sort, escreva um algoritmo para buscar uma numeração específica de sapato 
utilizando uma busca binária. O nome da variável que armazena o número do sapato 
procurado deve ser denominado chave. 
 
Disciplina: Técnicas de Programação 
 
 
 2 
Analise o desempenho do algoritmo insertion sort, utilizando busca sequencial, para o 
pior caso e o melhor caso. Explique cada caso utilizando um parágrafo de no máximo 
cinco linhas cada. 
 
1. Escreva o algoritmo insertion sort, considerando uma busca sequencial. 
 
A busca linear, tal como diz o nome, faz uma verificação sequencial de cada elemento, se 
o valor for encontrado, a busca é bem sucedida, mas se todos os elementos forem pesquisados e 
o valor desejado não, a pesquisa então será mal sucedida. 
 
Neste algoritmo de busca, temos uma verificação de todos os elementos de um vetor para 
saber se o elemento (key) está no vetor. 
 
 
 
Para a saída podemos utilizar uma condição para quando verdadeiro e falso: 
 
 
 
Já a ordenação, é o processo de rearranjar uma sequência de elementos em ordem 
ascendente ou descendente, de acordo com a chave de cada elemento. É aí que entra o Insertion 
Sort. 
 
Neste outro algoritmo, também utilizaremos o laço de repetição while, vamos usar o laço 
para fazer a troca em vetor[i] com as posições anteriores até que tenhamos a posição correta do 
vetor[i]. O elemento será inserido na posição i correta, estamos também considerando que o 
vetor está ordenado de 0 até i - 1. 
 
 
 
2. Considerando que as caixas do armazém já estão ordenadas, seguindo o algoritmo 
insertion sort, escreva um algoritmo para buscar uma numeração específica de sapato utilizando 
uma busca binária. O nome da variável que armazena o número do sapato procurado deve ser 
denominado chave. 
 
 
 3 
 
 
 
 
 
 
* Tamanho do vetor hipotético de 10. 
 
3. Analise o desempenho do algoritmo insertion sort, utilizando busca sequencial, para o 
pior caso e o melhor caso. 
 
O desempenho do algoritmo depende dos recursos (memória, tempo, etc) que ele utiliza 
para realizar o problema desejado, sendo o tempo a forma mais simples de se medir o seu 
desempenho. Podemos analisar os algoritmos de busca por meio da quantidade de vezes que os 
algoritmos acessam uma posição do vetor. 
 
Num exemplo em que temos um cadastro de 104 (dez mil) itens, se utilizássemos um 
algoritmo de busca sequencial, um elemento gastaria em média (104 + 1) / 2 = 5000.5 acessos. Já 
com a busca binária teríamos (log2 104) - 1 = 12.2 acessos. 
 
Fórmula para busca linear 
Fórmula para busca binária 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nota: 10,00 de um máximo de 10,00 (100%) 
Comentário: 
Olá José, 
 
Parabéns! Você compreendeu a solicitação e respondeu a proposta de maneira 
completa. 
 
Tutor Ead