Um Limite Superior para a Complexidade do ShellSort
Resumo
The worst-case time complexity of the ShellSort algorithm is known only for some specific sequences (a sequence is a parameter of the algorithm). Relating the algorithm to the Frobenius number concept, we present an algorithm for determining the maximum number of comparisons for any sequence and array to be ordered. We apply this method together with the empirical determination of complexity to analyze several sequences whose worst case complexity are known. We show that the empirical approach succeeded in determining the same complexities which are analytically known and presented its results for sequences with unknown worst-case time complexity.
Referências
Frank, R. M. Lazarus, R. B. (1960). A high-speed sorting procedure. Communications of the ACM, 3(1):20–22.
Gonnet, G. H. Baeza-Yates, R. A. (1991). Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley.
Hibbard, T. N. (1963). An empirical study of minimal storage sorting. Communications of the ACM, 6(5):206–213.
Incerpi, J. Sedgewick, R. (1983). Improved upper bounds on shellsort. Anais do 24o Annual Symposium on Foundations of Computer Science, p. 48–55.
Knuth, D. E. (1973). The Art of Computer Programming 3: Sorting and Searching. Addison-Wesley.
Oliveira, F. S. (2016). EMA - WebPage. [link]. [Último acesso: 10 de Março de 2018].
Papernov, A. A. Stasevich, G. V. (1965). A method of information sorting in computer memories. Problemy Peredachi Informatsii, 1(3):81–98.
Pratt, V. R. (1972). Shellsort and sorting networks. Relatório técnico, Documento DTIC.
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. Anais do 12o IFIP World Computer Congress on Algorithms, Software, Architecture-Information Processing, 1:449–457.
Gonnet, G. H. Baeza-Yates, R. A. (1991). Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley.
Hibbard, T. N. (1963). An empirical study of minimal storage sorting. Communications of the ACM, 6(5):206–213.
Incerpi, J. Sedgewick, R. (1983). Improved upper bounds on shellsort. Anais do 24o Annual Symposium on Foundations of Computer Science, p. 48–55.
Knuth, D. E. (1973). The Art of Computer Programming 3: Sorting and Searching. Addison-Wesley.
Oliveira, F. S. (2016). EMA - WebPage. [link]. [Último acesso: 10 de Março de 2018].
Papernov, A. A. Stasevich, G. V. (1965). A method of information sorting in computer memories. Problemy Peredachi Informatsii, 1(3):81–98.
Pratt, V. R. (1972). Shellsort and sorting networks. Relatório técnico, Documento DTIC.
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. Anais do 12o IFIP World Computer Congress on Algorithms, Software, Architecture-Information Processing, 1:449–457.
Publicado
26/07/2018
Como Citar
SOUZA, Raquel M.; OLIVEIRA, Fabiano S.; PINTO, Paulo E. D..
Um Limite Superior para a Complexidade do ShellSort. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 29-32.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3144.
