Comparação de caso médio do Merge Sort Top-Down 3 Subarrays vs Top-Down 2 Subarrays e Bottom Up

Trabalho desenvolvido durante a disciplina de Análise de algoritmos da Universidade Federal de Uberlândia.

• Intuição Consiste em dividir o problema em subpartes até alcançar o tamanho unitário e em seguida organizá-los de forma ordenada.

Objetivos: -Implementações Algoritmos Merge Sort com as seguintes variantes: - Top-Down com 3 subvetores - Top-Down com 2 subvetores - Bottom-Up com 2 subvetores

• Análise Caso Médio Tempo de execução médio do algoritmo Top-Down com 3 subvetores.
• Comparação com pares Comparação do tempo de execução médio do Merge Sort 3 splits versus demais algoritimos.
  • Teste de hipóteses
  • Comparação de custos gerais

Motivação

Relevancia da performance O(nlogn) Merge Sort para algoritmos de ordenação

Relevancia do Merge Sort para inspiração de novos algoritmos de ordenação

Metodologia

• Implementação
• Análise Empírica
• Comparação com MergeSort Top-Down e Bottom Up Tradicional
  • Teste de Hipóteses
    • Definição de Tamanho de amostras mínima significativa
    • Teste de aderência de Kolmogorov (Seleção de distribuição teórica que melhor se adequa aos dados experimentais.)
  • Estimação de custos gerais

Estimação de custos gerais Merge Sorts

Ilustração da estimação de custos gerais do Merge Sort.