Análise Empírica do Algoritmo Shellsort
Resumo
O objetivo deste trabalho é estudar a complexidade de tempo do algoritmo de ordenação Shellsort de um ponto de vista empírico. O desempenho teórico deste algoritmo depende de uma sequência de inteiros usada. Diversas sequências clássicas são estudadas na literatura, para a maioria das quais a complexidade de tempo é conhecida. No entanto, para algumas, ainda não se conhece a complexidade de tempo justa. Nossa abordagem foi a de estudar tais sequências clássicas empiricamente para ratificar as complexidades de tempo conhecidas e juntar evidências sobre aquelas desconhecidas.
Referências
Ciura, M. (2001). Best increments for the average case of shellsort. In Fundamentals of Computation Theory, pages 106–117. Springer.
Frank, R. M. and Lazarus, R. B. (1960). A high-speed sorting procedure. Communications of the ACM, 3(1):20–22.
Gonnet, G. H. and Baeza-Yates, R. A. (1991). Handbook of algorithms and data structures: in pascal and c. Hibbard, T. N. (1963). An empirical study of minimal storage sorting. Communications of the ACM, 6(5):206–213.
Incerpi, J. and Sedgewick, R. (1983). Improved upper bounds on shellsort. In Foundations of Computer Science, 1983., 24th Annual Symposium on, pages 48–55. IEEE.
Knuth, D. E. (1973). The art of computer programming 3: Sorting and searching.
Oliveira, F. S. (2016). EMA - WebPage. http://fabianooliveira.ime.uerj.br/ema. [última vez acessado: 07 de Junho de 2016].
Pratt, V. R. (1972). Shellsort and sorting networks. Technical report, DTIC Document.
Sedgewick, R. (1986). A new upper bound for shellsort. Journal of Algorithms, 7(2):159–173.
Shell, D. L. (1959). A high-speed sorting procedure. Communications of the ACM, 2(7):30–32.
Tokuda, N. (1992). An improved Shellsort. In 12th World Computer Congress on Algorithms, Software, Architecture-Information Processing, pages 449–457. N.-Holland.
Weiss, M. A. (1991). Short note empirical study of the expected running time of shellsort. The Computer Journal, 34(1):88–91.
Frank, R. M. and Lazarus, R. B. (1960). A high-speed sorting procedure. Communications of the ACM, 3(1):20–22.
Gonnet, G. H. and Baeza-Yates, R. A. (1991). Handbook of algorithms and data structures: in pascal and c. Hibbard, T. N. (1963). An empirical study of minimal storage sorting. Communications of the ACM, 6(5):206–213.
Incerpi, J. and Sedgewick, R. (1983). Improved upper bounds on shellsort. In Foundations of Computer Science, 1983., 24th Annual Symposium on, pages 48–55. IEEE.
Knuth, D. E. (1973). The art of computer programming 3: Sorting and searching.
Oliveira, F. S. (2016). EMA - WebPage. http://fabianooliveira.ime.uerj.br/ema. [última vez acessado: 07 de Junho de 2016].
Pratt, V. R. (1972). Shellsort and sorting networks. Technical report, DTIC Document.
Sedgewick, R. (1986). A new upper bound for shellsort. Journal of Algorithms, 7(2):159–173.
Shell, D. L. (1959). A high-speed sorting procedure. Communications of the ACM, 2(7):30–32.
Tokuda, N. (1992). An improved Shellsort. In 12th World Computer Congress on Algorithms, Software, Architecture-Information Processing, pages 449–457. N.-Holland.
Weiss, M. A. (1991). Short note empirical study of the expected running time of shellsort. The Computer Journal, 34(1):88–91.
Publicado
04/07/2016
Como Citar
DE SOUZA, Raquel M.; OLIVEIRA, Fabiano de S.; PINTO, Paulo Eustáquio D..
Análise Empírica do Algoritmo Shellsort. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 903-906.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9856.
