Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Ordenação - Coggle Diagram
Algoritmos de Ordenação
Força Bruta
Selection Sort
A lista é scanneada até ser encontrado o menor elemento, e este ser trocado com o primeiro elemento assumindo sua posição final na lista. Esse processo é repetido para o segundo elemento e assim por diante até toda a lista estar ordenada.
-
-
-
Bubble Sort
Compara elementos que são adjacentes na lista, e os troca se estiverem fora de ordem. Fazendo isso repetidamente os maiores elementos vão sendo levados até a última posição.
-
-
No pior caso, em que a lista está em ordem decrescente, ele será Θ(n²), então também é um algoritmo Θ(n²) para todas as entradas.
Podemos melhorar o bubble sort colocando uma condição que verifica se não teve alterações em uma iteração que percorre toda a lista, se nenhuma alteração tiver ocorrido a lista então está ordenada, e o algoritmo termina.
Uma primeira aplicação de algoritmos de força bruta frequentemente resulta em algoritmos que podem ser melhorados com uma quantidade pequena de esforço.
Diminuir para conquistar
É uma técnica baseada em explorar o relacionamento entre a solução de uma dada instância do problema e a solução de sua menor instância.
Ela pode ser explorada de cima para baixo ou de baixo para cima, podendo usar uma implementação recursiva, ou uma implementação iterada, começando com a solução da menor instância.
-
Insertion Sort
O array é divido em 2 partes, uma ordenada e a outra desordenada
Os valores da parte desordenada são selecionados e colocados em sua posição correta na parte ordenada.
Apesar de ser baseado em uma ideia recursiva, o algoritmo é mais eficiente quando implementado iterativamente.
-
A qtde. de comparações nesse algoritmo depende da entrada. O pior caso é um array de valores decrescentes, sendo assim no pior caso, ele fará o mesmo número de comparações que o Selection Sort. Θ(n²)
-
Sendo assim, Insertion Sort é mais eficiente em arrays que já estão relativamente ordenados.
Dividir para conquistar
-
Um caso comum de algoritmos dividir para conquistar: uma instância de um problema de tamanho n é dividido em duas instâncias de tamanho n/2.
Mais genericamente, uma instância de tamanho n pode ser dividida em b instâncias de tamanho n/b, com a delas para resolver( a e b são constantes; a ≥ 1 e b >1).
Assumindo que n é uma potência de b para simplificar a análise, nós temos a seguinte fórmula de recorrência para o tempo de execução: T(n) = aT(n/b) + f(n)
f(n) é uma função do tempo gasto em dividir uma instância de tamanho n em instâncias de tamanho n/b e combinar suas soluções.
A análise de eficiência de muitos algoritmos de dividir para conquistar é simplificada pelo Master Theorem.
Mergesort
Divide e ordena recursivamente o array em 2 metades, até o tamanho ser igual a 1
Quando o tamanho chega em 1 o processo de juntar(merge) os arrays, começa, e vai até todo o array estar completo.
-
-
-
Uma variação do mergesort chamada multiway mergesort é feita dividindo uma lista/array em mais de 2 partes, ordenando essas partes recursivamente e juntando (merge) elas novamente.