Please enable JavaScript.
Coggle requires JavaScript to display documents.
Força bruta e busca exaustiva - Coggle Diagram
Força bruta e busca exaustiva
Selection Sort
Procura o menor item e o coloca em primeiro, depois o menor item restante e o coloca em segundo e assim vai até o fim.
É um algoritmo Θ(n²), mas a troca em si dos itens é apenas Θ(n).
Bubble sort
Realiza-se comparações entre J e J+1 sucessivamente N-1 vezes. Quando J+1 é menor que J ele é trocado, dessa forma o maior elemento vai sendo jogado para a direita. Ao fim do loop, assume-se que o ultimo item vai ser o maior dos avaliados, portanto não há necessidade de se avalia-lo novamente, portanto, diminui-se o tamanho do loop em 1.
Podemos otimizar o algoritmo fazendo com que a lista pare de fazer comparações se durante um loop 0 trocas forem feitas.
Tem tempo Θ(n²) no pior dos casos e na média, mesmo otimizado.
Diminuir e conquistar
Na redução por uma constante o tamanho é reduzido por um valor fixo a cada iteração, normalmente por 1.
Na redução por fator constante, o tamanho é reduzido por um fator fixo, geralmente o 2.
Na redução por tamanho variável, o tamanho é reduzido a cada iteração varia, um bom exemplo é o do algoritmo de Euclides.
Insertion Sort
Um subarray do original é gerado e examinado da direita para a esquerda até se achar um elemento menor ou igual ao que estamos querendo inserir.
Tem um ótimo melhor caso e no pior faz o mesmo número de comparações que o selection sort.
Dividir para conquistar
Dividir o problema em sub problemas, de preferência de tamanho semelhante.
Resolver os sub problemas
Se necessário, unir as soluções para resolver o problema maior.
Mergesort
Divide um array em dois outros, resolve-os recursivamente, e, depois, junta-os novamente.
É mais eficiente para casos em que os arrays são grandes,nos piores casos ele se aproxima de um algoritmo de comparação genérico.
Consome uma grande quantidade de armazenamento extra.