Técnicas de Programação

Prévia do material em texto

1 
 
Disci 
 
Resolução / Resposta 
 
Aplicamos o conceito de algoritmo diariamente sempre que estabelecemos um 
planejamento mental para realizar uma determinada tarefa, considerando que deveremos 
executar um conjunto de passos até atingir o objetivo desejado. Entretanto, nem sempre a 
escolha do algoritmo certo é uma tarefa simples, portanto a análise do algoritmo a ser utilizado é 
o primeiro passo do planejamento antes de implementá-lo. Os usuários de um sistema 
computacional geralmente esperam que o sistema forneça as informações no menor tempo 
possível. Essa eficiência está diretamente relacionada à qualidade do algoritmo utilizado. 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. 
 
Os métodos de ordenação podem ser: 
 
• Internos: Onde os registros cabem na memória principal (in-place) e podem ser acessados 
imediatamente; 
• Externos: Onde os registros não cabem na memória principal (not in-place) e só podem ser 
consultados por meio de grandes blocos ou por acesso sequencial. 
 
Segundo Cormem (2002), 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. 
 
Fontes: 
 
CORMEN, T. H. et al. Introduction to Algoritms. Massachusetts Institute of Technology. 2. ed., 
2002. 
ASCENCIO, A. F. G.; Araújo, G. S. Estruturas de Dados: algoritmos, análise da complexidade e 
implementações em JAVA e C/C++.São Paulo: Pearson, 2010. 
 
Esse compilado apresenta de forma sucinta a importância da análise de algoritmos e 
técnicas de programação no nosso dia a dia. Após estudar a fundo sobre o tema, esperamos que 
você esteja apto a definir algoritmos compatíveis com as necessidades da área de TI, e de 
corporações como um todo. Nesse contexto, considere o texto acima a respeito da importância da 
escolha do algoritmo ser a mais assertiva possível para responder à questão proposta. 
 
1. Diferentes tipos de algoritmos de ordenação podem ser utilizados no desenvolvimento 
de soluções e tomada de decisão. Considerando que você deve realizar uma análise comparativa 
entre três algoritmos de ordenação: insertion sort, selection sort e merge sort, analise, 
utilizando a notação O, a complexidade de cada um dos três algoritmos selecionados, 
considerando o número de comparações, para o melhor e pior caso. Considere três tipos de 
entradas: vetor ordenado, vetor ordenado em ordem inversa e vetor ordenado aleatoriamente. 
 
Ordenação tipo Insertion Sort: ele percorre os elementos da esquerda para a direita, e os 
ordena conforme avança. Ele possui complexidade C(n) = O (n) no melhor caso e C(n) = O(n²) no 
pior caso, pois como ele precisa percorrer toda lista para cada elemento, onde (n * n = O(n²)), se a 
Disciplina: Técnicas de Programação 
 
 
 2 
lista tiver uma grande quantidade de itens, ele não terá um bom desempenho, mas é considerado 
estável, porque faz as trocas entre os vizinhos, assim ele mantém a ordem relativa dos valores 
iguais. 
 
Um fato interessante sobre o pior caso seria ordenar um array em ordem reversa, pois 
toda inserção deve percorrer toda a esquerda do array , trocando os elemtentos até encaixar o 
atual na primeira posição. Ordenação tipo Selection Sort: tal como o nome diz, vai 'selecionando' 
os menores elementos a cada iteração, e agrupa-os também da esquerda para a direita. Diferente 
do Insertion, ele tem a mesma complexidade para o melhor e pior caso, onde a complexidade é 
dada por C(n) = O(n²). 
 
Uma desvantagem dele é que ele não é um algoritmo estável, pois dependendo da troca, 
ele pode não manter a ordem relativa dos valores iguais. O selection efetua menos trocas que o 
insertion, já que demanda apenas uma troca por iteração, já o insertion efetua AO MENOS uma 
troca por iteração, já que ele deve efetuar as trocas para afastar cada elementos avaliado. 
Entretanto, em geral o insertion efetua menos comparações, pois nem sempre o elemento 
inserido deve ir até o final, além do mais, no pior dos casos, o array considerado seria aquele 
ordenado em ordem reserva. 
 
Na prática, por terem a mesma categoria de complexidade O(n²), o Insertion apresenta 
um melhor desempenho que o Selection. Ordenação tipo Merge Sort: ele já pertence a uma 
categoria de algoritmos mais eficientes, pois requerem uma menor quantidade de comparações e 
trabalham com uma maior quantidade de dados. O merge é conhecido pela estratégia de dividir 
para conquistar, onde ele divide o problema em pedaços menores, resolve-os e depois os junta 
(merge) nos resultados. Ele tem a complexidade C(n) = O(n log n) para todos os casos. 
 
2. A Indústria O algoritmo quick sort é considerado muito eficiente para uma grande 
variedade de situações, entretanto, no pior caso ele realiza O(n2) operações. O melhor caso 
acontece quando as partições têm sempre o mesmo tamanho, balanceadas, e o pior caso, 
quando o pivô é sempre o maior ou menor elemento, ou seja, quando estão desequilibradas as 
partições. Considerando as vantagens e desvantagens desse algoritmo de ordenação, responda:. 
 
a. Qual o principal cuidado que deve ser observado ao utilizar esse algoritmo? 
b. Existem, no mínimo, três alternativas para minimizar a ocorrência do pior caso. 
Cite e explique uma delas. 
 
Como ele se baseia numa rotina chamada particionamento, que significa escolher um 
número qualquer presente no array (pivot) e colocá-lo numa posição de forma que todos os 
elementos à esquerda são menores ou iguais e todos os elemtnos a direita são maiores. O pior 
caso do quick sort O(n²) se manifesta quando o pivot sempre divide o array em duas porções de 
tamanho 0 e n-1, para minimizar esse tipo de ocorrência, devemos escolher melhor o pivot, que 
vamos explicar abaixo. 
 
Quando o pivot já está ordenado, ou seja, quando ele executa de forma recorrente 
péssimas partições, que significa colocar o pivot em um lugar que não há elementos a sua 
esquerda e que há n - 1 a sua direita. Um exemplo seria pegar um array já ordenado e sempre 
escolhemos o pivot como sendo o primeiro elemento ou quando ele está ordenado de forma 
reserva e fazemos a mesma escolha do pivot. 
 
Assim, embora raro, o pior caso precisa encontrar algumas condições, que é quando o 
array já está ordenado e nós escolhemos o primeiro elemento como pivot. O pivot acarretará em 
particionamentos ruins, temos então que escolher o pivot de forma aleatório ou mediana de três 
elementos do array. Aleatoria temos a probabilidade p = 1/n * 1/(n - 1) * 1/(n - 2)...., o que 
 
 
 3 
tornaria difícil (mas não impossível) de ser escolhido o primeiro. Um outra boa possibilidade é 
escolher pela mediana de três, que nada mais é que o valor central do conjunto de dados, 
teríamos então um estratégia que evitaria de escolhermos um pivot ruim e a ocorrência do pior 
caso. 
Por fim, a terceira alternativa, para o médio e melhor caso seria aquele que mais se 
aproxima do Merge Sort, ou seja, se o pivot sempre ficar no meio do array, teríamos uma árvore 
na recursão em que a esquerda e a direita tem metade do tamanho do array, onde o melhor caso 
seria log n execuções do particiona, que é O(n). Se aplicarmos as técnicas acima, temos uma alta 
probabilidade de não tiramos um péssimo pivot e alta de tirar no caso médio, que é O(n * log n). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nota: 10,00 de um máximo de 10,00 (100%) 
Comentário: 
Parabéns! Você compreendeu a solicitação e respondeu a proposta de maneira 
completa. 
 
Abraços, 
Tutora EaD