sistemas

Ordenação: Mergesort
SIN 213 – Projeto de Algoritmos
Universidade Federal de Viçosa – UFV
Sistemas de Informação
Prof. Tácito Neves [e-mail] Bibliografia
•

ZIVIANI, N. Projeto de algoritmos: com implementações em Pascal e C.
Pioneira Thomson Learning, 2004.
– Capítulo 2: Seção 2.5.

•

DEITEL, H. M.; DEITEL, P. J. Java: como programar. 6. ed. São Paulo: Pearson
Prentice Hall. 2005.
– Capítulo 16: Seção 16.3.3.

•

Notas de Aula do Prof. Paulo Feofiloff (IME-USP)
– Projeto de Algoritmos em C
• Disponível em: http://www.ime.usp.br/~pf/algoritmos/aulas/mrgsrt.html

•

Site da disciplina “Algorithms and Data Structures” do Prof. Robert Sedgewick
– http://www.cs.princeton.edu/courses/archive/spring09/cos226/info.html

•

Animações de Algoritmos de Ordenação
– http://www.sorting-algorithms.com/
– http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
– http://coderaptors.com/?Sorting_algorithms

Ordenação – Algoritmos Eficientes
•

Relembrando:
– Problema de Ordenação
• Rearranjar um vetor v[ 0 .. n-1 ] de tal modo que ele fique em ordem crescente, ou seja, de tal modo que tenhamos v[ 0 ] ≤ . . . ≤ v[ n – 1 ].
– Algoritmos de ordenação elementares resolvem o problema em tempo proporcional a n2 – O( n2 )
• Insertion Sort ( Ordenação por inserção )
• Selection Sort( Selection Sort )
– MUITO LENTOS
– Algoritmos de ordenação mais eficientes
• Resolvem o problema de ordenação em tempo proporcional a n log2n
• Ordenação por Intercalação – Merge Sort
• Ordenação Rápida – Quick Sort

Ordenação por intercalação – Mergesort
•

Idéia básica
– Dividir o array em duas metades
– Ordenar cada metade recursivamente
– Intercalar as duas metades ordenadas

Von Neumann

Intercalação (merge) de vetores ordenados
•

Problema:
– Dados dois vetores crescentes (ordenados) v[ p .. q - 1 ] e v[ q .. r – 1 ], rearranjar v[ p .. r – 1 ] em ordem crescente.

•

Poderíamos resolver este problema basta