Please enable JavaScript.
Coggle requires JavaScript to display documents.
Abordagem por Força Bruta - Coggle Diagram
Abordagem por Força Bruta
Ordenação
Diminuir e Conquistar
A técnica de diminuir e conquistar é baseada na exploração da relação entre uma solução para uma determinada instância de um problema e uma solução para sua instância menor.
Existem três variações principais de diminuição e conquista:
Diminuir por um fator constante
reduzindo uma instância do problema pelo mesmo fator constante em cada iteração do algoritmo. Na maioria das aplicações, esse fator constante é igual a 2.
variável a diminuição do tamanho
O padrão de redução de tamanho varia de uma iteração de um algoritmo para outra. O algoritmo de Euclides para calcular o maior divisor comum fornece um bom exemplo dessa situação.
Diminuir por uma constante
O tamanho de uma instância é reduzido pela mesma constante em cada iteração do algoritmo. Normalmente, essa constante é igual a 1.
Insertion Sort
É claramente baseado em uma ideia recursiva, é mais eficiente implementar esse algoritmo de baixo para cima, ou seja, iterativamente.
Começando com A [1] e terminando com A [n - 1], A [i] é inserido em seu lugar apropriado entre os primeiros i elementos da matriz que já foram classificados (mas, ao contrário do selection sort, geralmente não estão em suas posições finais).
1 more item...
Dividir e Conquistar
É provavelmente a técnica de design de algoritmo geral mais conhecida.
Algoritmos de divisão e conquista funcionam de acordo com
seguinte plano geral:
Os subproblemas são resolvidos
Se necessário, as soluções para os subproblemas são combinadas para obter uma solução
ao problema original.
Um problema é dividido em vários subproblemas do mesmo tipo, idealmente de aproximadamente do mesmo tamanho.
Mergesort
É um exemplo perfeito de uma aplicação bem-sucedida da técnica de dividir para conquistar.
Ele classifica um determinado array A [0..n - 1] dividindo-o em duas metades, classificando cada uma delas recursivamente e, em seguida, mesclando as duas matrizes menores classificadas em uma única classificada.
Selection Sort
Começamos o selection sort examinando toda a lista fornecida para encontrar seu menor elemento e trocá-lo pelo primeiro elemento, colocando o menor elemento em sua posição final na lista ordenada.
Em seguida, examinamos a lista, começando com o segundo elemento, para encontrar o menor entre os últimos n - 1 elementos e trocá-lo pelo segundo elemento, colocando o segundo menor elemento em sua posição final.
O Selection Sort é um algoritmo (n²) em todas as entradas.
Entretanto, o número de trocas é apenas (n), ou, mais precisamente, n - 1 (um para cada repetição do loop i). Esta propriedade distingue o selection sort positivamente de muitos outros algoritmos de ordenação.
Bubble Sort
Compara os elementos adjacentes da lista e os troca se estiverem fora de ordem.
Fazendo isso repetidamente, acabamos “borbulhando” o maior elemento para a última posição da lista.
O número de comparações chave para o bubble sort é o mesmo para todos os arrays de tamanho n; é obtido por uma soma que é quase idêntica à soma para o selection sort
O número de trocas de chave, no entanto, depende da entrada. No pior caso de arrays decrescentes, é igual ao número de comparações de chave
