Implementação de Algoritmo Híbrido AOH a partir de Algoritmos Conhecidos

...

Segue o gráfico:

[pic 4]

3.5. InsertionSortvs SelectionSort vs BubbleSort vsMergeSort

A seguir, o gráfico comparativo dos quatro algoritmos analisados nesta primeira etapa do trabalho:

[pic 5]

Como pode se observar através destes resultados, constatamos de maneira inquestionável a eficiência do princípio “Dividir para Conquistar” no algoritmo merge sort. A diferença nos resultados obtidos é estrondosa, enquanto que os demais algoritmos têm seu trabalho acrescido de maneira quadrática, com valores bem acimas de um segundo, o merge sort teve em seu maior tempo bem menos de um segundo.

3.6. Algoritmo híbrido (AOH)

Com base nos resultados dos testes, o algoritmo que teve um melhor desempenho depois do merge sort foi o insertion sort, que além do mais foi o melhor para entradas de tamanho 1000, a exemplo.

A minha estratégia para desenvolvimento do algoritmo híbrido AOH foi o de utilizar o algoritmo merge sort em um vetor de tamanho [80.000, n] e os demais elementos [0, 80.000] serão processados não mais pelo merge sort, mas pelo insertion sort. A ideia aqui é esclarecer a proporção em que o algoritmo se torna eficiente, nesta minha análise, 2n/5.

A seguir o gráfico com os resultados:

[pic 6]

O algoritmo híbrido se justifica apesar do pequeno acréscimo em tempo, já que diminui consideravelmente o número de chamadas recursivas (o que implica numa carga de trabalho maior no processamento do algoritmo). Isso observando a proporção adequada, pois como se pode constatar no gráfico, em intervalos [0.025n, 0.5n] há uma grande discrepância no tempo de execução.

4. Conclusão

Feitas todas as análises, pode-se inferir que os algoritmos mais simples (insertion sort, selection sort e bubble sort) são bons em determinadas condições, a se dizer, entradas menores (pouco usual já que a maioria dos softwares do mercado que possam ser auxiliados com tais algoritmos utilizam-se de grande volume de dados).

Vimos também que algoritmos do tipo divisão e conquista tem um desempenho excepcional se comparado aos algoritmos mais simples, a exemplo o merge sort. O ponto alto deste trabalho foi se obter um algoritmo híbrido adequado, aceitável que pudesse reduzir consideravelmente o número de chamadas recursivas do merge sort. Com base na coleta dos resultados, o meu escolhido foi o insertion sort, na proporção de 2n/5 (n o tamanho da entrada) com uma certa discrepância de tempo em uma certa faixa de valores. Ainda assim, para entradas grandes o algorimo se sobressaiu bem.

5. Bibliografia

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Algoritmos: Teoria e Prática.

Campus, 2nd edition.