IMPACTO DAS RESTRIÇÕES DE HARDWARE NA EFICIÊNCIA DE ALGORITMOS DE ORDENAÇÃO

UM ESTUDO COMPARATIVO

Autores

Resumo

A ordenação eficiente de dados tem desempenhado um papel vital em muitas aplicações, desde pesquisas rápidas até a otimização do desempenho de algoritmos mais complexos. No entanto, com o constante crescimento dos conjuntos de dados e informações disponíveis na Internet, a seleção do algoritmo de ordenação torna-se uma tarefa crucial, dada a diversidade de opções disponíveis. Assim, a comparação de algoritmos em diferentes cenários ajuda a identificar suas vantagens e limitações, contribuindo para uma escolha mais precisa em cada contexto. O objetivo deste trabalho é, portanto, realizar uma análise comparativa da eficiência dos algoritmos de ordenação Merge Sort e Quick Sort, a fim de identificar qual é o mais adequado para diferentes cenários de uso. A metodologia consiste em experiências utilizando duas máquinas virtuais e uma máquina física, onde são avaliados o consumo de memória e o tempo de execução. Os resultados mostram que o Merge Sort, apesar de consumir mais memória em todos os cenários avaliados, tem melhor desempenho em termos de tempo médio de execução nos casos com mais elementos, enquanto o Quick Sort mantém sua vantagem consistente em termos de consumo médio de memória nos três cenários avaliados.

Biografia do Autor

  • Jonas Lima Cavalcante, Universidade Federal do Ceará-UFC, Campus Quixadá

    Mestrando em Computação, pelo Programa de Pós-graduação em Computação (PCOMP), da Universidade Federal do Ceará – UFC, Campus Quixadá.

  • Rubens Fernandes Nunes, Universidade Federal do Ceará-UFC, Campus Quixadá

    Professor Associado D Nível 1 da Universidade Federal do Ceará (UFC - Campus Quixadá) do curso Ciência da Computação, desde 2013. Possui doutorado em Ciência da Computação (2006-2012), mestrado em Ciência da Computação (2004-2006) e graduação em Computação (2000-2003) pela Universidade Federal do Ceará (UFC). Em 2008/2009, participou do programa de doutorado sanduíche (CNPq) na Universidade da Califórnia em Riverside (UCR). Possui experiência na área de Computação Gráfica e tem atuado principalmente nos seguintes temas: Animação de Personagens, Simulação Física, Controle de Movimento, Aprendizado de Máquina, Aprendizado por Reforço, Realidade Aumentada, Unity, Processamento de Movimentos Capturados e Análise de Vibrações.

  • Emanuel Ferreira Coutinho, Universidade Federal do Ceará-UFC, Campus Quixadá

    Professor Associado na Universidade Federal do Ceará (UFC), lotado no Campus Quixadá. Possui graduação em Ciência da Computação pela Universidade Estadual do Ceará (2000). Mestre em Ciência da Computação pela Universidade Estadual do Ceará (2003), trabalhando com temas relacionados a grafos, escalonamento e roteamento de veículos, e modelagem matemática. Doutor em Ciência da Computação pela Universidade Federal do Ceará (2014), trabalhando com Computação em Nuvem, definindo métricas e metodologias para análise de desempenho da elasticidade. Também participa como professor permanente no Programa de Pós-Graduação em Computação (PCOMP), na Universidade Federal do Ceará, Campus Quixadá, e do Programa de Pós-Graduação em Tecnologia Educacional (PPGTE), do Instituto UFC Virtual. Suas áreas de interesse são Computação em Nuvem, Análise de Desempenho, Sistemas de Informação e Engenharia de Software. Atuou no desenvolvimento de sistemas e de processos de software. Também é implementador do MPS.BR, especialista em Gerenciamento de Projetos (UFRJ) e Project Management Professional (PMP).

Referências

ADHIKARI, POOJA; POOJA, A. (2007). Review On Sorting Algorithms-A comparative study on two sorting algorithms. Mississippi State, Mississippi, v. 4.

AFONSO, J. M. D. (2009). Optimização de estruturas multidimensionais de dados em ambientes OLAP. (Doctoral dissertation, ISCTE-Instituto Universitario de Lisboa (Portugal)).

AL-KHARABSHEH, K. S., ALTURANI, I. M., ALTURANI, A. M. I., & ZANOON, N. I. (2013). Review on sorting algorithms a comparative study. International Journal of Computer Science and Security (IJCSS), 7(3), 120-126.

BENTLEY, J. (2016). Programming pearls. Addison-Wesley Professional.

BHARGAVA, A. Y. (2018). Entendendo Algoritmos: Um guia ilustrado para programadores e outros curiosos. Novatec Editora.

CENTURION, A. M. (1998). Análise de desempenho de algoritmos paralelos utilizando plataformas de portabilidade. (Doctoral dissertation, Universidade de São Paulo).

DE AZEVEDO, R. C. (2016). Análise dos algoritmos de ordenação: buscando a eficiência em sistemas de supermercados.

DIKA, A., & PREVALLA, B. (2010, November). The impact of memory and processor in determining the performance of programs. In 2010 IEEE 26-th Convention of Electrical and Electronics Engineers in Israel (pp. 000015-000018). IEEE.

DRUMOND, P. M. L. D. L. (2012). Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo. (Master's thesis, Universidade Federal do Rio Grande do Norte).

FOLADOR, J. P., NETO, L. N. P., AND JORGE, D. C. (2014). Aplicativo para análise comparativa do comportamento de algoritmos de ordenação. Revista Brasileira de Computação Aplicada, 6(2):76–86.

GEEKSFORGEEKS (2023). Merge sort, https://www.geeksforgeeks.org/merge-sort/

GOLDREICH, O. (2008). Computational complexity: a conceptual perspective. ACM Sigact News, 39(3):35–39.

MARCELLINO, M., PRATAMA, D. W., SUNTIARKO, S. S., AND MARGI, K. (2021). Comparative of advanced sorting algorithms (quick sort, heap sort, merge sort, intro sort, radix sort) based on time and memory usage. In 2021 1st International Conference on Computer Science and Artificial Intelligence (ICCSAI), volume 1, pages 154–160.

NAKASHIMA, E. Y. (2017). Avaliação de atividades de programação submetidas em mooc com emprego de técnicas de visualização. B.S. thesis, Universidade Tecnológica Federal do Paraná.

POLLMAN, H. J. S. (2009). Probabilistic cost analysis of logic programs. Ingeniare. Revista chilena de ingeniería, 17(2):195–204.

RAJPUT, I. S., KUMAR, B., AND SINGH, T. (2012). Performance comparison of sequential quick sort and parallel quick sort algorithms. International Journal of Computer Applications, 57(9):14–22.

RAFAEL, A. O. (2022). As implicações econômicas e sociais resultantes da implementação de inteligência artificial pelo estado, em especial pelo setor regulador. Master’s thesis, ISCTE-Instituto Universitario de Lisboa (Portugal).

SUBANDIJO, S. (2011). Efisiensi algoritma dan notasi o-besar. ComTech: Computer, Mathematics and Engineering Applications, 2(2):849–858.

TOSCANI, L. V. AND VELOSO, P. A. (2001). Complexidade de algoritmos. Sagra-Luzzatto. Porto Alegre.

YANG, Y., YU, P., AND GAN, Y. (2011). Experimental study on the five sort algorithms. In 2011 Second International Conference on Mechanic Automation and Control Engineering, pages 1314–1317.

ZERANSKI, S. AND SANCAK, I. E. (2021). Prudential supervisory disclosure (psd) with su- pervisory technology (suptech): lessons from a fintech crisis. International Journal of Disclosure and Governance, pages 1–21

Downloads

Publicado

2025-03-10

Edição

v. 17 n. 2 (2024): RETEC - Revista de Tecnologias

Seção

Artigos