Ordenação
Professor Paulo Gomide
27 de outubro de 2015
Sumário
• Ordenação:
– Considerações iniciais e definições;
– Métodos de ordenação:
• Inserção;
• Mergesort.
– Comparação entre os métodos apresentados.
Considerações Iniciais
• Objetivos:
– Definir e apresentar o problema da ordenação;
– Introduzir os conceitos de métodos de ordenação simples
e eficiente;
– Apresentar e analisar um método simples e um método
eficiente, comparando os mesmos.
Definição e Objetivos da Ordenação
Algumas Aplicações de Ordenação
• Testar se todos os elementos de um conjunto são distintos;
• Remover duplicações de elementos de um conjunto;
• Encontrar o k-ésimo menor item de um conjunto;
• Interseção e união de conjuntos;
• Busca eficiente.
Métodos para Ordenação
Ordernação por Inserção
Ordernação por Inserção
Ordenação por Inserção: Análise
Divisão e Conquista
• Deseja-se revolver um problema com uma entrada grande;
• Para facilitar a resolução do problema, a entrada é dividida
em pedaços menores (DIVISÃO);
• Cada pedaço da entrada é então tratado separadamente
(CONQUISTA);
• Ao final, os resultados parciais são combinados para gerar
o resultado final procurado.
Divisão e Conquista
• Técnica consistem em 3 passos:
1. Divisão: Dividir o problema original em subproblemas menores;
2. Conquista: Resolver cada subproblema independentemente
(em geral, recursivamente);
3. Combinação: Combinar as soluções encontradas, compondo
uma solução para o problema original.
Mergesort: Exemplo
• A execução do Mergesort pode ser facilmente descrita
por uma árvore binária, onde:
- Cada nó representa uma chamada recursiva do Mergesort;
- O nó raiz é a chamada inicial;
- Os nós folhas são vetores de 1 ou 2 números (casos bases).
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Exemplo
Mergesort: Análise
• A altura h da árvore de execução é O(log n);
• A quantidade de operações em cada nível da árvore é
assintoticamente igual a O(n);
• Logo: algoritmo é O(n log n), em todos os casos.
Mergesort: Análise
• Complexidade: O(n log n)
• Vantagens
– O(n log n) em todos os casos;
– Indicado para aplicações que tem restrição crítica de tempo;
– Fácil implementação.
• Desvantagens
– Utiliza memória auxiliar – O(n);
– Na prática pode ser mais lento que o Quicksort no caso médio.
Referências
• Knuth, The Art of Computer Programming, Vol. 3: Sorting and
Searching, 2nd Ed, MA: Addison-Wesley, 1998;
• Aulas do professor Antonio Alfredo Ferreira Loureiro, DCC/UFMG,
Algoritmos e Estruturas de Dados II, 2007;
• Aulas do professor Túlio Toffolo, UFOP, Algoritmos e Estruturas de
Dados I, 2011;
• Aulas do professor Tim Roughgarden, Stanford University, Design
and Analysis of Algorithms I, 2012.