Sorts
Edson Prestes
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Divisão e conquista
Divide um problema em subproblemas independentes, resolve-os e combina as soluções obtidas em uma solução para o problema original.
Isso resulta em um processo recursivo de decomposições e recombinações.
Pode ser aplicado em problemas de:
buscas em tabelas, como buscas seqüencial e binária;
classificação, como classificação por seleção (selectionsort), por
intercalação (mergesort) e por particionamento (quicksort);
multiplicação (de matrizes e de números binários, por exemplo);
seleção (para determinar máximo e mínimo, etc.).
posicionamento de braço manipuladores;
planejamento de caminhos em robótica móvel, etc
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Somatório dos elementos de uma lista.
Considere uma lista L de elementos do tipo inteiro.
Se L tem no máximo 1 elemento, a soma de seus elementos é trivial.
Caso contrário, este somatório pode ser visto como sendo a soma dos elementos da
primeira metade de L, chamada L1, com os elementos da segunda metade, chamada L2.
somatorio(L):= se curta( L ) // Tem comprimento de no máximo 1 ? então retorna ( L ) // retona zero se L é vazia, ou o próprio elemento. senão retorna (soma(somatorio(sublist1(L)), somatorio(sublist2(L)))).
Onde soma(r1, r2) = r1+ r2
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Classificação de listas por intercalação de sublistas.
O algoritmo recebe como entrada uma lista L e devolve esta lista classificada.
Se L tem comprimento no máximo 1, então L já está classificada.
Caso contrário, a lista L é dividida em duas listas aproximadamente do mesmo tamanho,
L1 e L2 correspondendo a primeira e a segunda metades de L, respectivamente.
L1 e L2 são recursivamente classificadas e intercaladas a fim de obter uma versão
classificada da lista de entrada.
Complexidade de