Please enable JavaScript.
Coggle requires JavaScript to display documents.
Força Bruta, Diminuir-e-Conquistar, Dividir e conquistar, brute force and…
Força Bruta
Ordenação
Selection Sort
Começamos o Selection Sort examinando toda a lista dada 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 com o segundo elemento, colocando o segundo menor elemento em sua posição final.
Bubble sort
Compara os elementos adjacentes da lista e trocá-los se estiverem fora de ordem. Fazendo isso repetidamente, acabamos “borbulhando” o maior elemento para a última posição da lista. O próximo passo borbulha o segundo maior elemento e assim por diante, até que depois de n - 1 passos a lista seja ordenada.
Na verdade, mesmo entre os métodos de classificação elementares, o Bubble Sort é uma escolha inferior e, se não fosse por seu nome atraente, você provavelmente nunca teria ouvido falar dele.
A força bruta é uma abordagem direta para resolver um problema, geralmente com base na declaração do problema e nas definições dos conceitos
envolvidos.
para alguns problemas importantes -por exemplo, ordenação, pesquisa, multiplicação de matrizes, comparação de strings- a abordagem de força bruta produz algoritmos razoáveis de pelo menos algum valor prático sem limitação no tamanho da instância.
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.
Uma vez que essa relação seja estabelecida, ela pode ser explorada de cima para baixo ou de baixo para cima.
-
Insertion Sort
Tudo o que precisamos é encontrar um
posição apropriada para A [n - 1] entre os elementos ordenados e inseri-lo lá.
Isso geralmente é feito examinando o subarray classificado da direita para a esquerda até que o primeiro elemento menor ou igual a A [n - 1] seja encontrado para inserir A [n - 1] logo após esse elemento.
Embora o Insertion Sort seja claramente baseado em uma ideia recursiva, é mais eficiente implementar esse algoritmo de baixo para cima, ou seja, iterativamente.
Dividir e conquistar
-
Mergesort
Mergesort é um exemplo perfeito de uma aplicação bem-sucedida da técnica de dividir para conquistar.
Ele ordena um determinado array A [0..n - 1], dividindo-o em duas metades A [0..n / 2 - 1] e A [n / 2..n - 1], ordenando cada um deles recursivamente, e, em seguida, mescla os dois arrays ordenados menores em um único ordenado.
-
-