Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de ordenação - Coggle Diagram
Algoritmos de ordenação
-
Decrease-and-Conquer
-
-
-
InsertionSort
-
-
-
+eficiente quando implementado 'bottom up', começando com A(1) e terminando com A(n-1).
Ideia geral: Existirá um 'sub-array' com os elementos já ordenados. A cada novo elemento que será encaixado nesse sub-array, será feito uma busca sequencial da direita para esquerda a procura da posição onde ele não perturbe a ordenação. Repetir até o sub-array ser o novo array, agora ordenado.
Divide-and-Conquer
- O problema é dividido em vários subproblemas do mesmo tipo.
- Os subproblemas são solucionados.
- Se necessário, as soluções dos subproblemas são combinadas para produzir a solução do problema original.
Ótima sinergia com processamento paralelo, onde é possível delegar os subproblemas para mais de um processador.
Análise assintótica
b = instâncias de tamanho n/b, das quais 'a' precisam ser resolvidas. Com isso temos:
T(n) = aT(n/b) + f(n),
onde f(n) é uma função que conta o tempo gasto na divisão de instâncias de tamanho n em instâncias de tamanho n/b e combinando suas soluções.
Teorema Mestre:
............./ Θ(n^d) se a < b^d,
T(n) ∈ < Θ(n^d log n) se a = b^d,
.............\ Θ(n^logb a) se a > b^d.
obs.: gambiarrei uma chave.
MergeSort
Ideia geral: Separa um array A[n] em 2 A[n/2] e os ordena recursivamente para depois juntá-los em um único array ordenado.
Merge: Dois apontadores são atribuídos para os 2 arrays, na hora de juntá-los eles são comparados e o menor deles é adcionado ao novo array. O index do que foi adcionado é incrementado. Repetir até completar.
-
Pros:
-Para n's grandes o número de comparações feitos é aproximadamente 0.25n (em relação ao pior caso).
-Estabilidade.
Cons:
-Requer uma quantidade linear n de espaço extra, para o array pronto.