Sorts

Complexidade de Algoritmos
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