sistemas

1115 palavras 5 páginas
Ordenação: Mergesort
SIN 213 – Projeto de Algoritmos
Universidade Federal de Viçosa – UFV
Sistemas de Informação
Prof. Tácito Neves tacito.neves@ufv.br 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

Relacionados

  • SISTEMA
    3632 palavras | 15 páginas
  • Sistema mes
    3913 palavras | 16 páginas
  • sistemas
    673 palavras | 3 páginas
  • sistema
    1948 palavras | 8 páginas
  • Sistemas
    523 palavras | 3 páginas
  • Sistemas
    2065 palavras | 9 páginas
  • Sistemas
    1404 palavras | 6 páginas
  • sistemas
    1073 palavras | 5 páginas
  • Sistema
    1796 palavras | 8 páginas
  • SISTEMAS
    459 palavras | 2 páginas